1 solutions
-
0
题目大意
这道题目要求在坐标的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); });
-
- 1
Information
- ID
- 7
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 37
- Accepted
- 10
- Uploaded By