本文主要是介绍uva10559 Blocks（区间DP 增加维度），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
每次可以选择一个区间（连续相同的序列）消除，得分为 len*len；问最大得分。
分析：
紫书P298-299，很详细。
LRJ代码：
#include<bits/stdc++.h>
using namespace std;const int maxn = 200 + 5;
int n, A[maxn], d[maxn][maxn][maxn];// blocks i~j, plus k blocks whose color is the same as block j
int dp(int i, int j, int k) {if(i > j) return 0;int& ans = d[i][j][k];if(ans >= 0) return ans;int p = j;while(p >= i && A[p] == A[j]) p--;p++; // leftmost position that block j's color can "extend" toans = dp(i, p-1, 0) + (j-p+k+1)*(j-p+k+1); // click block jfor(int q = i; q < p; q++)if(A[q] == A[j] && A[q] != A[q+1]) // remove q+1~p-1 firstans = max(ans, dp(q+1, p-1, 0) + dp(i, q, j-p+k+1));return ans;
}int main() {int T;scanf("%d", &T);for(int kase = 1; kase <= T; kase++) {scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d", &A[i]);memset(d, -1, sizeof(d));printf("Case %d: %d\n", kase, dp(0, n-1, 0));}return 0;
}
这篇关于uva10559 Blocks（区间DP 增加维度）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
