华为 9.21 9月21日 机试 第三题 动态规划 简单解法

思路：
根据坐标进行dp递推而不是根据树的编号，这是关键。
dp[i]代表第i个坐标之前，最大的价值（只考虑树的左右边界全包含在坐标i之前的树）。
坐标从第一棵树的右边往后移动，每新包含一棵树，进行一次判断：
1、新树的价值（value）小于覆盖范围内其他树的价值（dp[右边界 - 1] - dp[左边界]），则不种植该树。
2、新树的价值（value）大于覆盖范围内其他树的价值（dp[右边界 - 1] - dp[左边界]），则移除其他树，种植这棵新树，更新dp[右边界]。
i移到最后时，dp[终点]就是最优种植方案的价值。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

bool fun(vector<int> &a,vector<int> &b){
    if(a[0] < b[0] ) return true;
    return false;
}

int main() {
    //输入处理
    int n;
    cin >> n;
    if( n <= 0 ){
        cout << 0;
        return 0;
    }
    //len记录所有树的右边界能覆盖的最远的距离
    int len = 0;
    vector<vector<int>> data(n + 1 ,vector<int>(3,-1));
    for(int i = 1 ; i < n + 1 ; i ++ ){
        cin >> data[i][0];
    }
    for(int i = 1 ; i < n + 1 ; i ++ ){
        cin >> data[i][1];
        //最大坐标是覆盖最远的那棵树的右边界，注意，不一定是越靠后的树覆盖越远
        len = max( len , data[i][0] + data[i][1]);
    }
    for(int i = 1 ; i < n + 1 ; i ++ ){
        cin >> data[i][2];
    }
    //按每棵树适合种植的位置排序
    sort(++data.begin(),data.end(),fun);
    //dp[i]代表第i个坐标之前，最大的价值（只考虑树的范围全包含在坐标i之前的树）
    vector<int> dp( len + 1,0);
    //计算第i个坐标之前，最大的价值
    for(int i = data[1][0] + 1 ; i < len + 1 ; i ++ ){
        for( int j = 1 ; j < n + 1 && data[j][0] < i  ; j ++ ){
            //向后移动坐标i，如果有新的树被包含在i内，则计算这棵树的价值data[j][2]和这棵树范围内所有其他树的价值dp[i - 1] - dp[data[j][0] - data[j][1]]哪个更大，取较大的
            if( data[j][0] + data[j][1] == i && data[j][2] > dp[i - 1] - dp[data[j][0] - data[j][1]]){
                dp[i] = max( dp[i] , dp[ data[j][0] - data[j][1] ] + data[j][2] );
            }
        }
        //如果dp[i]有更新，则肯定大于dp[i - 1]，否则坐标i前所有树的价值等于坐标i-1前所有树的价值
        dp[i] = max(dp[i],dp[i - 1]);
    }
    //最后一个坐标前的所有树的最大价值即为结果
    cout << dp[len];
    return 0;
}

/*
5
2 3 6 5 7
1 1 3 1 1
20 20 100 70 60
结果150

4
2 3 4 5 
1 1 1 2
50 10 40 70
结果120
*/