@Acqua
2019-02-23T08:39:32.000000Z
字数 1873
阅读 931
动态规划
给定一个长度为的序列和个公差，如果能够在序列中找到一个连续的、公差为给定公差的等差数列（长度大于1），就可以把整个数列都从序列中删掉。求最大删除数量。
设给定公差数组为。
预处理出表示从开始，公差为的最长连续等差数列长度。
表示区间内最多可删掉的数量。
初始化：。
对于区间，删除有多种情况（完备性证明：因为最终序列将被分解为长度为2（最小的偶数）或3（满足题意的最小奇数）的子串，所以以下枚举可以覆盖所有情况。）
情况：可以一起删除（前提：区间全部删除），则该区间可全部删除。
枚举断点。
情况：可以一起删除（前提：区间全部删除），则该区间可删除。
情况：可以一起删除（前提：区间全部删除），则该区间可删除。
情况：可以一起删除（前提：区间和全部删除），则该区间可全部删除。
取上述所有答案（包括初始化）最大值。
// La Pluie#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int N = 300 + 5;int a[N], il[N][N], dp[N][N];int main(){int T, n, m;scanf("%d", &T);while(T--){memset(dp, 0, sizeof(dp));memset(il, 0, sizeof(il));scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i = 1; i <= m; i++){int ecart;scanf("%d", &ecart);for(int j = 1; j < n; j++){for(int k = j + 1; k <= n; k++){if(a[k] - a[j] == ecart){il[j][k] = 1;}}}}for(int l = 1; l <= n; l++){for(int i = 1; i + l - 1 <= n; i++){int j = i + l - 1;dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);if(il[i][j] && dp[i + 1][j - 1] == j - i - 1) dp[i][j] = j - i + 1; // 情况1for(int k = i + 1; k < j; k++){dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]); // 由于是取最大值，所以没有先后关系，所以合并dp[i][k]和dp[k+1][j]来更新答案的过程可以放在循环中if(il[i][k] && dp[i + 1][k - 1] == k - i - 1) dp[i][j] = max(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j] + 2); // 情况2if(il[k][j] && dp[k + 1][j - 1] == j - k - 1) dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j - 1] + 2); // 情况3if(il[i][k] && il[k][j] && a[j] - a[k] == a[k] - a[i] && dp[i + 1][k - 1] == k - i - 1 && dp[k + 1][j - 1] == j - k - 1) dp[i][j] = j - i + 1; // 情况4}}}printf("%d\n", dp[1][n]);}return 0;}