1 solutions

  • 0
    @ 2024-9-3 20:20:17

    题目大意

    这道题目要求在坐标的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]。 为了求解这个问题,我们可以采用动态规划的方法。以下是具体的步骤和分析:

    1. 线段的表示与排序 首先,我们需要将每条线段表示为一个结构体,包含起点、终点和价值。然后,将所有线段按照结束位置(即 p[i] + r[i])从小到大排序。这一步的目的是为了在后续的动态规划中,能够方便地找到不重叠的线段。

    2. 动态规划的状态定义 定义一个数组 dp,其中 dp[i] 表示前 i 条线段中,选择互不重叠的线段所能获得的最大总价值。

    3. 状态转移方程 对于第 i 条线段,有两种选择:

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

    1. 寻找不重叠的线段 为了高效地找到最后一条不与当前线段重叠的线段 j,我们可以使用二分查找。因为线段已经按照结束位置排序,二分查找可以在较短的时间内完成。

    2. 初始化与边界条件 dp[0] = w[0],表示只选择第一条线段时的最大价值。 对于 i > 0,按照状态转移方程逐步计算 dp[i]。

    3. 最终结果 最终的答案为 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

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

    Information

    ID
    7
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    7
    Tags
    # Submissions
    37
    Accepted
    10
    Uploaded By