$f[i][j] = f[u][j - (i - 1 - u)] + w[a[u]][a[i]]$
一句话解释该方程:
- $f[u][j - (i - 1 - u)]$隐含了$a[u+1..i-1]$已经删除,此时$a[u]$和$a[i]$相邻,还需从$a[1…u]$删除$j-(i-1-u)$个数。
如果看到这里如果你已经懂了状态是如何转移的,那么下面的解释不必再看。
关于状态转移,我们假设$f[i][j]$是前$i$个数($1…i$)恰好删除$j$个数后的最大价值。
假设我们从$f[u][*]$转移到$f[i][j]$,那么从$(u+1…i-1)$的数必然已经删除($a[u]$与$a[i]$相邻才能转移)。
此时已经删除了$(i-1-(u+1)+1=i-1-u)$个数,而我们本来总共要删除$j$个数,那么我们就需要前$u$($1…u$)个数中删除$(j-(i-1-u))$个数。
正向逻辑比较好理解
那么转移方程可得$f[i][j] = f[u][j - (i - 1 - u)] + w[a[u]][a[i]]$
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 205;
int n, k, m, a[N], w[N][N], f[N][N];
signed main() {
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// cout << setiosflags(ios::fixed) << setprecision(2);
// cout << setw(2) << setfill('0');
cin >> n >> k >> m;
for (int i = 1; i <= m; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> w[i][j];
}
}
for (int i = 1; i <= m; ++i) {
for (int j = 0; j <= k; ++j) {
for (int u = 1; u < i; ++u) {
if (j - (i - 1 - u) >= 0) {
f[i][j] = max(f[i][j], f[u][j - (i - 1 - u)] + w[a[u]][a[i]]);
}
}
}
}
int ans = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 0; j <= k; ++j) {
ans = max(ans, f[i][j]);
}
}
cout << ans << "\n";
return 0;
}