題意：有n個帶顏色的方塊，同種顏色的方塊連成一個區域，每次可以消除一個區域的方塊x，然后得到分數x2，右邊的方塊左移，然后問求最大的分數。

思路：區間dp，dp（i，j，k）表示區間（i，j）在右邊添上k個顏色與j相同的方塊的最優解。對于每個狀態，如果消去j，狀態轉移到dp（i，p-1，0）+（j-p+k+1）2，要不然枚舉q<p使得a[q]=a[j]且a[q]不等于a[q+1],轉移到dp（q+1，p-1，0）+dp（i，q，j-p+k+1）；

code：

#include <bits/stdc++.h> using namespace std;typedef long long ll; typedef unsigned long long ull; typedef long double ld;const int INF=0x3fffffff; const int inf=-INF; const int N=1000000; const int M=205; const int mod=1000000007; const double pi=acos(-1.0);#define cls(x,c) memset(x,c,sizeof(x)) #define cpy(x,a) memcpy(x,a,sizeof(a)) #define ft(i,s,n) for (int i=s;i<=n;i++) #define frt(i,s,n) for (int i=s;i>=n;i--) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lrt rt<<1 #define rrt rt<<1|1 #define middle int m=(r+l)>>1 #define lowbit(x) (x&-x) #define pii pair<int,int> #define mk make_pair #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout);int n,v[M]; int dp[M][M][M]; int sol(int l,int r,int k){if (l>r) return 0;int& ans=dp[l][r][k];if (ans) return ans;ans=sol(l,r-1,0)+(k+1)*(k+1);frt(i,r-1,l){if (v[i]==v[r])ans=max(ans,sol(l,i,k+1)+sol(i+1,r-1,0));}return ans; } int main() {int T;scanf("%d",&T);ft(ca,1,T){scanf("%d",&n);ft(i,1,n) scanf("%d",&v[i]);cls(dp,0);printf("Case %d: %d\n",ca,sol(1,n,0));} }

總結

以上是生活随笔為你收集整理的uva 10559——Blocks的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。