AcWing 3499. 序列最大收益(DP)

柔情只为你懂 2024-05-08 06:27 7阅读 0赞

##### 题目 #####

给定一个长度为 m 的整数序列 a1,a2,…,am。

序列中每个元素的值 ai 均满足 1≤ai≤n。

当一个值为 i 的元素和一个值为 j 的元素相邻时，可以产生的收益为 wi,j。

现在，我们可以从序列中删除最多 k 个元素，删除一些元素后，原本不相邻的元素可能会变得相邻。

序列的收益和为所有相邻元素对产生的收益之和，例如一个长度为 3 的整数序列 1,3,2 的收益和为 w1,3+w3,2。

请问，通过利用删除操作，能够得到的序列的最大收益和是多少？

**输入格式**  
第一行包含三个整数 n,k,m。

第二行包含 m 个整数 a1,a2,…,am。

接下来 n 行，每行包含 n 个整数，其中第 i 行第 j 列的数表示 wi,j。

**输出格式**  
输出序列的最大收益和。

**数据范围**  
对于 30% 的数据，1≤n,k,m≤20。  
对于 100% 的数据，1≤n,k,m≤200，0≤wi,j≤107，1≤ai≤n。  
数据保证 wi,j=wj,i，wi,i=0。

**输入样例：**

4 1 3
    1 4 2
    0 3 0 1
    3 0 0 0
    0 0 0 0
    1 0 0 0

**输出样例：**

**样例解释**  
初始序列收益和为 w1,4+w4,2=1+0=1。

删除中间的 4 后，序列 1,2 的收益和为 w1,2=3。

##### 思路 #####

观察数据范围后发现，如果枚举每一个元素会不会被删去，时间复杂度是指数级的，只适用于数据量20以内的，为了解决问题，时间复杂度要控制在3次方以内，由此可以想到动态规划。  
首先是状态的划分，我们可以定义dp\[i\]\[j\]代表以a\[i\]为结尾元素，删去j个元素后的最大目标值，注意元素a\[i\]是不能删去的;  
然后是状态的转化，可以在区间 \[i,j)中找一个下标u，假设a\[u\]到a\[i - 1\]的元素全部删除，这样转到下一状态，即dp\[i\]\[j\] = max(dp\[i\]\[j\], dp\[u\]\[j - (i - u - 1)\] + w\[a\[u\]\]\[a\[i\]\])

##### 代码 #####

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    const int N = 210;
    
    int n, k, m;
    int a[N];
    int w[N][N], dp[N][N];
    
    int main() {
        
        scanf("%d%d%d", &n, &k, &m);
        for(int i = 1; i <= m; i ++) scanf("%d", &a[i]);
        
        for(int i = 1; i <= n; i ++){
        
            for(int j = 1; j <= n; j ++) {
        
                scanf("%d", &w[i][j]);
            }
        }
        
        memset(dp, -0x3f, sizeof(dp));
        //dp[i][j]代表以a[i]为结尾元素，删去j个元素后的最大目标值，注意元素a[i]是不能删去的
        dp[1][0] = 0;
        //第一个元素一定不需要删去，所以直接从第二个元素开始即可
        for(int i = 2; i <= m; i ++) {
        
            for(int j = 0; j <= k; j ++) {
        
                //中间可以删去的元素位置
                for(int u = 1; u < i; u ++) {
        
                    //可以删的元素个数一定要大于将要删除的元素个数
                    if(j >= i - u - 1) dp[i][j] = max(dp[i][j], dp[u][j - (i - u - 1)] + w[a[u]][a[i]]);
                }
            }
        }
        int res = 0;
        for(int i = 0; i <= k; i ++) res = max(res, dp[m][i]);
        
        printf("%d\n", res);
        return 0;
    }