題目描述

n個木塊排成一列，每個木塊都有一個顏色。

每次，你都可以點擊一個木塊，這樣被點擊的木塊以及和它相鄰并且同色的木塊就會消除。 如果一次性消除了k個木塊，那么就會得到k*k分。

給定你一個游戲初始狀態，請你求出最高得分是多少。

解析

區間dp
首先可以把同色合并，從而將數列轉化為一個由若干段組成的新的數列
用dp[i][j][k]表示新數列中在加上后面有k個與第j段顏色相同的木塊的情況下，第i到j段的最大得分
那么就可以不斷把第r段嘗試與之前的同色段連接消除，并繼續遞歸：

for(int i=l;i<r;i++){if(co[i]==co[r]){dp[l][r][k]=max(dp[l][r][k],solve(l,i,len[r]+k)+solve(i+1,r-1,0));}}

從而完成本題

代碼

#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <string> #include <queue> #include <string> #include<map> #define ll long long #define mem(a,b) memset(a,b,sizeof(a)); #define ull unsigned ll using namespace std; const int N=250; int m,n,ans; int dp[N][N][N],a[N]; int len[N],co[N],tot; int solve(int l,int r,int k){if(l>r) return 0;if(dp[l][r][k]) return dp[l][r][k];if(l==r) return dp[l][r][k]=(len[l]+k)*(len[l]+k);dp[l][r][k]=solve(l,r-1,0)+(len[r]+k)*(len[r]+k);for(int i=l;i<r;i++){if(co[i]==co[r]){dp[l][r][k]=max(dp[l][r][k],solve(l,i,len[r]+k)+solve(i+1,r-1,0));}}return dp[l][r][k]; } int main(){scanf("%d",&m);for(int p=1;p<=m;p++){scanf("%d",&n);mem(dp,0);mem(len,0);mem(co,0);tot=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(i==1||a[i]!=a[i-1]){co[++tot]=a[i];len[tot]=1;}else len[tot]++;}printf("Case %d: %d\n",p,solve(1,tot,0));} }

心得

本題參考了題解。。。
主要就是這個dp的定義和向前遞歸的思想沒有想到
（本來一直在枚舉長度找遞推式awa）
而其實遞推能做的dp遞歸應該也可以，時間復雜度不會差太多（也就億點點 ）
所以：

dp要優先考慮遞歸！！！

thanks for reading！

總結

以上是生活随笔為你收集整理的不止代码：ybtoj-消除木块（区间DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

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