序列最大收益（冬季每日一题 3）

给定一个长度为 $m$ 的整数序列 $a_1,a_2,\dots ,a_m$。

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

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

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

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

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

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

第二行包含 $m$ 个整数 $a_1,a_2,\dots ,a_m$。

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

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

数据范围
对于 30% 的数据，$1\le n,k,m\le 20$。
对于 100% 的数据，$1\le n,k,m\le 200，0\le w_{i,j}\le 10^7，1\le a_i\le n$。
数据保证 $w_{i,j}=w_{j,i}，w_{i,i}=0$。

输入样例：

4 1 3
1 4 2
0 3 0 1
3 0 0 0
0 0 0 0
1 0 0 0
1
2
3
4
5
6

输出样例：

3
1

样例解释
初始序列收益和为 $w_{1,4}+w_{4,2}=1+0=1$。

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

---

思路

状态表示 $f[i][j]$

• 集合：只考虑前$i$个数，共删除了$j$个数，且不删除第$i$个数的所有方案的集合
• 属性：$max$

状态计算

• 考虑$i$前面的那个数
  可以将集合划分为
  $i$前面的数没有,$i$前面的数字是第 $1,\mathrm{2...},x,...,i-1$
  假如$i$前面的数字是第$x$个数字
  所以$[x$~$i]$之间就删除了 $i-x-1$ 个数
  由于此时的状态是$f[i][j]$所以$[1$~$x]$之间就要删除 $j-(i-x-1)$ 个数字
  所以 $f[i][j]=f[x][j-(i-x-1)]+w[a[x]][a[i]]$

#include
#include

using namespace std;

const int N = 210;

int n, k, m;
int a[N], w[N][N], f[N][N];

int main(){
    
    memset(f, -0x3f, sizeof f);
    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]);
    
    f[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)
                    f[i][j] = max(f[i][j], f[u][j-(i-u-1)]+w[a[u]][a[i]]);
    
    int res = 0;
    for(int i = 0; i <= k; i++)
        res = max(res, f[m][i]);
    
    printf("%d\n", res);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34