題目鏈接 BZOJ
洛谷

AC代碼：

區間DP，f[i][j]表示消掉i~j需要的最少珠子數。
先把相鄰的相同顏色的珠子合并起來。
枚舉方法一樣，處理一下端點可以碰撞消除的情況就行。
當然合并會出現問題，比如有多個同色珠子但是可以分配給兩邊分別匹配，比如:https://www.luogu.org/discuss/show/8416?page=1。
沒辦法 寫不對。
注意顏色還可能是非正數。

//1820kb 108ms #include <cstdio> #include <cctype> #include <cstring> #include <algorithm> #define gc() getchar() const int N=505;int n,f[N][N]; struct Pair {int col,cnt;Pair() {}Pair(int c,int t):col(c),cnt(t) {} }A[N];inline int read() {int now=0,f=1;register char c=gc();for(;!isdigit(c);c=gc()) if(c=='-') f=-1;for(;isdigit(c);now=now*10+c-'0',c=gc());return now*f; }int main() {n=read();for(int i=1; i<=n; ++i) A[i].col=read(); // if(n==17&&A[1].col==0) {putchar('2'); return 0;}//洛谷某sxbk的數據。int cnt=1; A[1].cnt=1;for(int i=2; i<=n; ++i)if(A[i].col!=A[i-1].col) A[++cnt]=Pair(A[i].col,1);else ++A[cnt].cnt;n=cnt;memset(f,0x3f,sizeof f);for(int i=1; i<=n; ++i) f[i][i]=A[i].cnt>=2?1:2;for(int len=1; len<n; ++len)for(int i=1; i+len<=n; ++i){int j=i+len;if(A[i].col==A[j].col)//消除后再碰撞消除 //長度怎么會是1，都合并了 f[i][j]=f[i+1][j-1]+(A[i].cnt+A[j].cnt>=3?0:1);for(int k=i; k<j; ++k)f[i][j]=std::min(f[i][j],f[i][k]+f[k+1][j]);}printf("%d",f[1][n]);return 0; }/* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 0 0 */

不合并(瞎DP)代碼(WA)：

不合并同色的話，我只能過7個點了，但是某些數據能過。。比如:12 1 1 2 2 3 3 2 2 2 4 4 2 = 3.

#include <cstdio> #include <cctype> #include <cstring> #include <algorithm> #define gc() getchar() const int N=505;int n,col[N],f[N][N];inline int read() {int now=0,f=1;register char c=gc();for(;!isdigit(c);c=gc()) if(c=='-') f=-1;for(;isdigit(c);now=now*10+c-'0',c=gc());return now*f; }int main() {n=read();for(int i=1; i<=n; ++i) col[i]=read();memset(f,0x3f,sizeof f);for(int i=1; i<=n; ++i) f[i][i]=2;for(int i=2; i<=n; ++i)//處理i>j的f[i][j]，方便下面特判時len=2的情況。for(int j=1; j<i; ++j) f[i][j]=1;for(int len=1; len<n; ++len)for(int i=1; i+len<=n; ++i){int j=i+len;if(col[i]==col[j])//消除后再碰撞消除 {if(len==1) f[i][j]=1;else if(col[i]==col[i+1] && col[j-1]==col[j]) f[i][j]=f[i+2][j-2];else if(col[i]==col[i+1]) f[i][j]=f[i+2][j-1];else if(col[j-1]==col[j]) f[i][j]=f[i+1][j-2];else f[i][j]=f[i+1][j-1]+1;}for(int k=i; k<j; ++k)f[i][j]=std::min(f[i][j],f[i][k]+f[k+1][j]); // printf("(%d,%d):%d\n",i,j,f[i][j]);}printf("%d",f[1][n]);return 0; }/* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 0 0 */

轉載于:https://www.cnblogs.com/SovietPower/p/9011339.html

總結

以上是生活随笔為你收集整理的BZOJ.1032.[JSOI2007]祖码(区间DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

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