2022.09.21-秋招-互不重叠线段的最大价值

TaZi SU @ 7 months ago

题目大意

这道题目要求在坐标的x轴上选择若干条互不重叠的线段，使得所选线段的总价值最大

思路

每条线段由中点的横坐标、半径长度和价值决定。具体来说，线段的起点和终点分别为 p[i] - r[i] 和 p[i] + r[i]。选择的线段必须满足任意两条线段不重叠，即对于任意两条线段 i 和 j，要么 p[i] + r[i] <= p[j] - r[j]，要么 p[j] + r[j] <= p[i] - r[i]。为了求解这个问题，我们可以采用动态规划的方法。以下是具体的步骤和分析：

线段的表示与排序 首先，我们需要将每条线段表示为一个结构体，包含起点、终点和价值。然后，将所有线段按照结束位置（即 p[i] + r[i]）从小到大排序。这一步的目的是为了在后续的动态规划中，能够方便地找到不重叠的线段。
动态规划的状态定义 定义一个数组 dp，其中 dp[i] 表示前 i 条线段中，选择互不重叠的线段所能获得的最大总价值。
状态转移方程 对于第 i 条线段，有两种选择：

不选择第 i 条线段：此时 dp[i] = dp[i-1]。选择第 i 条线段：则需要找到最后一条不与第 i 条线段重叠的线段 j，此时 dp[i] = dp[j] + w[i]。最终，dp[i] 取这两种情况的最大值。

寻找不重叠的线段 为了高效地找到最后一条不与当前线段重叠的线段 j，我们可以使用二分查找。因为线段已经按照结束位置排序，二分查找可以在较短的时间内完成。
初始化与边界条件 dp[0] = w[0]，表示只选择第一条线段时的最大价值。对于 i > 0，按照状态转移方程逐步计算 dp[i]。
最终结果 最终的答案为 dp[n-1]，即选择前 n 条线段中，互不重叠的线段所能获得的最大总价值。

代码

Java代码

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class node {
	public int p, r, w;
}
class cmp implements Comparator<node> {	//自定义排序
	public int compare(node a, node b) {
		if (a.p < b.p)
			return -1;
		return 1;
	}
}
class Main {
	public static node[] a;
	public static int M = 10010, n;
	public static int[] dp;

	public static int func() {
		int ans = 0;
		// 枚举每个线段i
		for (int i = 0; i < n; i++) {
			// 枚举其他线段j
			for (int j = 0; j < i; j++) {
				// 如果可以转移
				if (a[i].p - a[i].r >= a[j].p + a[j].r) {
					// 转移
					dp[i] = Math.max(a[i].w + dp[j], dp[i]);
				}
			}
			// 所有线段为结尾的取最优解
			ans = Math.max(ans, dp[i]);
		}
		return ans;
	}

	public static void main(String[] args) {
		dp = new int[M];
		a = new node[M];
		for (int i = 0; i < M; i++)
			a[i] = new node();
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		for (int i = 0; i < n; i++) {
			a[i].p = scanner.nextInt();
		}
		for (int i = 0; i < n; i++) {
			a[i].r = scanner.nextInt();
		}
		for (int i = 0; i < n; i++) {
			a[i].w = scanner.nextInt();
		}
		// 对中点排序
		Arrays.sort(a, 0, n, new cmp());
		// dp[0] = a[0].w;
		for (int i = 0; i < n; i++) {
			dp[i] = a[i].w;
		}
		System.out.println(func());
	}
}

Python代码

class seg:
  p,r,w=0,0,0
n=int(input())
dp=[0 for i in range(n)]
a=[seg() for i in range(n)]
b=list(map(int,input().split()))
for i in range(n):
  a[i].p=b[i]
b=list(map(int,input().split()))
for i in range(n):
  a[i].r=b[i]
b=list(map(int,input().split()))
for i in range(n):
  a[i].w=b[i]
a.sort(key=lambda x:x.p)
ans=0
for i in range(n):
  dp[i]=a[i].w
for i in range(n): #枚举每个线段i
  for j in range(i): #枚举其他线段j
    if a[i].p-a[i].r>=a[j].p+a[j].r: #转移
      dp[i]=max(a[i].w+dp[j],dp[i])
  ans=max(ans,dp[i]) #所有线段为结尾的取最优解
print(ans)

C++代码

#include<bits/stdc++.h>
using namespace std;

const int M = 1e4 + 4;
int dp[M];
int n;

struct node{
    int p, r;
    int w;
	// 自定义排序
    bool operator< (node &b)const{
        return p < b.p;
    }
}a[M];
// 动态规划
int func(){
    int ans = 0;
    // 枚举每个线段i
    for(int i = 0; i < n; i++){
        // 枚举其他线段j
        for(int j = 0; j < i; j++){
            // 如果可以转移
            if(a[i].p - a[i].r >= a[j].p + a[j].r){
                // 转移
                dp[i] = max(a[i].w + dp[j], dp[i]);
            }
        }
        // 所有线段为结尾的取最优解
        ans = max(ans, dp[i]);
    }
    return ans;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i].p;
    }
    for(int i = 0; i < n; i++){
        cin >> a[i].r;
    }
    for(int i = 0; i < n; i++){
        cin >> a[i].w;
    }
    // 对中点排序
    sort(a, a + n);
    // dp[0] = a[0].w;
    for(int i = 0; i < n; i++){
        dp[i] = a[i].w;
    }
    cout << func() << endl;
    return 0;
}

Js代码

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';

process.stdin.on('data', (data) => {
  input += data;
  return;
});
process.stdin.on('end', () => {
  function cmp(a, b) {
    return a.p - b.p;
  }
  function seg() {
    this.p = 0;
    this.r=0;
    this.w=0;
  }
  let inputArray = input.split('\n');
  let n = Number(inputArray[0]);
  var a = new Array();
  var b = new Array();
  for (let i = 0; i < n; i++)
    a[i] = new seg();
  for (let i = 0; i < n; i++)
    b[i] = Number(inputArray[1].split(' ')[i]);
  for (let i = 0; i < n; i++)
    a[i].p = b[i];
  for (let i = 0; i < n; i++)
    b[i] = Number(inputArray[2].split(' ')[i]);
  for (let i = 0; i < n; i++)
    a[i].r = b[i];
  for (let i = 0; i < n; i++)
    b[i] = Number(inputArray[3].split(' ')[i]);
  for (let i = 0; i < n; i++)
    a[i].w = b[i];
  a.sort(cmp);
  let dp = new Array();
  for (let i = 0; i < n; i++) {
    dp[i] = a[i].w;
  }
  let ans = 0;
  // 枚举每个线段i
  for (let i = 0; i < n; i++) {
    // 枚举其他线段j
    for (let j = 0; j < i; j++) {
      // 如果可以转移
      if (a[i].p - a[i].r >= a[j].p + a[j].r) {
        // 转移
        dp[i] = Math.max(a[i].w + dp[j], dp[i]);
      }
    }
    // 所有线段为结尾的取最优解
    ans = Math.max(ans, dp[i]);
  }
  console.log(ans);
});

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

动态规划

# Submissions

Accepted

Uploaded By

TaZi

1 solutions

题目大意

思路

代码

Information

Status

Development

Support