AcWing夏季·序列最大收益

2021年05月13日 11时50分

标签：动态规划

### 题目描述
给定一个长度为$$m$$的整数序列$$a_1,a_2,\cdots,a_m$$。

序列中每个元素的值$$a_i$$均满足$$1\leq a_i \leq n$$。

当一个值为$$i$$的元素和一个值为$$j$$的元素相邻时，可以产生的收益为$$w_{i,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
```

###输出样例
```
3
```

###样例解释
```
初始序列收益和为 w1,4+w4,2=1+0=1。
删除中间的 4后，序列 1,2 的收益和为 w1,2=3。
```

### 解题思路
动态规划，定义状态：
```
dp[i][j] := 已经考察了前i个元素，删除了j个元素，且保留第i个元素所能获得的最大收益
```
由于$$a_i$$前面可以为$$[a_1,a_k]$k < i$$$之中的任何一个数，或者没有数，因此状态转移方程为
```
dp[i][j] = max{dp[k][j- (i-k-1)] + w[a[k]][a[i]]} for k < i if j-(i-k-1) >= 0
```
另外，可以得知序列中，第一个元素是必选的：
> 假设选择第一个元素为$$a_j(j > 1)$$时，能够得到最大收益。

> 由于$$w_{i, j} \geq 0$$，因此把$$a_1$$加到$$a_j$$之前，一定能够减少删除元素的数量，同时增大最大收益。

> 这就和假设产生了矛盾，因此$$a_1$$必选。

因此可以设边界条件为`dp[1][0] = 0`（此时$$a_1$$旁边没有数，收益为$$0$$），然后从第2个数开始进行状态转移即可。
状态转移时，由于$$a_1$$必选，因此$$k$$从1开始遍历即可。

时间复杂度：$$O(n^3)$$

#### 代码
````cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 205;
int a[N];
int w[N][N];
int dp[N][N];
// dp[i][j] := 已经考察了前i个元素，删除了j个元素，且保留第i个元素所能获得的最大收益
// dp[i][j] = max{dp[k][j- (i-k-1)] + w[a[k]][a[i]]} for k < i if j-(i-k-1) >= 0
int main(void){
    int n, k, m;
    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[1][0] = 0;
    for(int i = 2; i <= m; i++){
        for(int j = 0; j <= k; j++){
            for(int k = 1; k < i; k++){
                if(j-(i-k-1) >= 0){
                    dp[i][j] = max(dp[i][j], dp[k][j-(i-k-1)] + w[a[k]][a[i]]);   
                }
            }
        }
    }
    int res = -1;
    for(int i = 0; i <= k; i++){
        res = max(res, dp[m][i]);
    }
    printf("%d\n", res);
    return 0;   
}
````

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

AcWing夏季·序列最大收益

所有评论

暂无评论

新增评论