思路对比
通过将Y总的DP改写成DFS,对照一下思路的不同:
我的思路:搜索每个元素,知道每个元素的前一个元素,每个元素根据剩余可删除元素的限制,可选可不选。
Y总思路:知道每个元素的前一个元素,但不是逐个搜索,而是直接枚举搜索下一个元素
对比:虽然2种思路都要知道上一个元素,但Y总思路更好,抓住了最大价值只和相邻2个元素有关的特点,放弃了逐个枚举的思路,改而直接枚举下一个元素,Y总复杂度是$O(k^2 * m)$,而我的思路复杂度是$O(k*m^2)$,表面看起来都是$O(n^3)$,但一般来说k比m小,所以Y总思路更优。。。
#include <iostream>
#include <cstring>
using namespace std;
using LL = long long;
const int maxn = 201;
int w[maxn][maxn], f[maxn][maxn];
int a[maxn];
int m;
int dfs(int p, int k) {
if(f[p][k] != -1) return f[p][k];
int ans = 0;
for(int i = 0; i <= k; i++) {
int ne = p + 1 + i;
if(ne > m) break;
ans = max(ans, dfs(ne, k-i)+w[a[p]][a[ne]]);
}
f[p][k] = ans;
return ans;
}
int main(void) {
int n, k;
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(f, -1, sizeof f);
printf("%d\n", dfs(0,k));
return 0;
}
算法1
(DFS+记忆化剪枝) $O(n^3)$
搜索每个元素,根据剩余可选元素k的数量,可选可不选
选了的话,k- -
又因为价值由相邻元素决定,所以要保存前一个被选元素的索引
// dfs(i, k, last, sum)
// if k <= 0, dfs(i+1, k, i, sum+w[last][i])
// if k > 0, dfs(i+1,k-1,last,sum) : dfs(i+1,k,i,sum+w[last][i])
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
using LL = long long;
const int maxn = 201;
int w[maxn][maxn], f[maxn][maxn][maxn];
int a[maxn];
int m;
int dfs(int i, int k, int l) {
if(i == m+1) return 0;
if(f[i][k][l] != -1) return f[i][k][l];
int t = 0;
if(k > 0) t = dfs(i+1,k-1,l);
t = max(t, w[a[l]][a[i]] + dfs(i+1,k,i));
f[i][k][l] = t;
return t;
}
int main(void) {
int n, k;
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(f, -1, sizeof f);
printf("%d\n", dfs(1,k,0));
return 0;
}
算法2
(DP) $O(n^3)$
// 1. enum all elements, delete or not
// dfs(i, k, l)
// max(k > 0 ? dfs(i+1,k-1,l) : 0, dfs(i+1,k,l)+w[a[l]][a[i]] );
// 公式显而易见了。。。
// 时间复杂度: k * (1+..+m) = k*m**2 = 200**3 = 8e6
C++ 代码
#include <iostream>
using namespace std;
using LL = long long;
const int maxn = 202;
int w[maxn][maxn], f[2][maxn][maxn];
int a[maxn];
int m;
int main(void) {
int n, k;
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]);
}
for(int i = m; i >= 0; i--) {
for(int j = 0; j <= k; j++) {
for(int l = 0; l < i; l++) {
f[i&1][j][l] = max((j > 0 ? f[(i+1)&1][j-1][l] : 0), f[(i+1)&1][j][i]+w[a[l]][a[i]]);
}
}
}
printf("%d\n", f[1][k][0]);
return 0;
}
// 1. enum all elements, delete or not
// dfs(i, k, l)
// max(k > 0 ? dfs(i+1,k-1,l) : 0, dfs(i+1,k,l)+w[a[l]][a[i]] );
// 公式显而易见了。。。
// 时间复杂度: k * (1+..+m) = k*m**2 = 200**3 = 8e6