不老的傳說問題
Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Discuss
Problem Description
一位先知告訴dynamic，在遙遠的地方，有一處不老的泉水，在那裡，他可以找到他人生的意義。按照先知的指引，dynamic出發了。翻越雪山，穿過叢林，渡過汪洋，終于來到了沙漠的最深處。按照先知的說法，泉水就在這個地方。然而除了無盡的黃沙之外，什麼都沒有。
dynamic幾乎絕望了，他盲目地走着，突然來到了一圈奇異的巨石前，在巨石陣的中央清晰地傳來泉水輕快的聲音。巨大的石頭擋住了去路，dynamic無法前進了。突然間，本來無色的石頭閃爍出絢麗奪目的光芒，與泉水聲交織成詩一般的樂章。又過了一刹那，色彩消失了。
“這裡面一定有什麼秘密，我要把石頭染成剛才的顔色！”dynamic對自己說。他還清楚地記得每一塊石頭的顔色。智慧女神雅典娜這是出現了，遞給他一把神奇的刷子，說“這把刷子每次可以把連續的不超過K塊石頭刷成一種新顔色，新刷的顔色會覆寫原來的顔色。用最少的次數，恢複石陣的光彩，你就會找到不老的泉水。”
dynamic意識到這并不是一件很容易的事，他出發得太匆忙，忘了帶上手提電腦。你能幫助他嗎？
Input
第1行包含3個整數N，C，K。N是石頭的個數，C是顔色的種類，K是每次最多刷過的石頭的個數。1<=N<=200，1<=C，K<=N。
第2行包含N個整數，分别是N塊石頭最終的顔色，按照順時針的順序。顔色是1到C之間的一個整數，整數間用一個空格隔開。開始的時候，所有的石頭都是無色的。
Output
輸出一個整數，為需要的最少次數。
Example Input
5 2 3
1 2 1 2 1 Example Output
3 Hint
樣例說明：設5塊石頭的編号分别是1，2，3，4，5。可以先把5，1，2染成顔色1；再把2，3，4染成顔色2；最後把3染成顔色1。
要求的是怎麼通過刷顔色，使得形成最終的序列，我們已經知道可以給連續的不超過k塊石頭一次性塗色，求經過最少的次數使得空白序列形成給定的序列
此題跟hdu 2476有些類似，但是這道題目中的石頭是圍成的圈形的，也就是說12345是連續的，23451也是連續的，是以我們可以将數組開大一倍，令a[i+n]=a[i],就能實作循環的問題，我們設dp[i][j]為i-j區間内轉換成給定序列的最小步數，那麼先假設i位置是要塗色的dp[i][j]=dp[i+1][j]+1,如果發現在這個區間内有a[k]==a[i]，說明i,k最終顔色相同，如果i->k區間在給定一次刷的最大區間内，那麼我們就可以一次刷好，dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j])
考慮區間[L,R]，如果[L]和[L+1,R]中的某一個顔色相同，才有可能減少刷的次數。那麼從左到右枚舉這個和[L]相同顔色的位置，[L,R]的次數就可以變成[L+1,k]+[k+1,R]了。可以想象成[L]是依靠另一個同顔色的位置來獲得免刷的可能，則這個位置必定是距離它K個位置之内的。如果長度為K的某一段區間[L,L+K-1]中有多段分散的同顔色的，有沒有可能是刷一次那個顔色，然後其他不同顔色的再截成一段一段的，将次數給組合起來呢？其實這種情況在枚舉依靠位置k的時候已經考慮了，假設你選擇依靠[L+K-1]，那麼[L+1,L+K-2]中還有和[L]是同顔色的，而區間[L+1,L+K-1]已經是最優，其他的同色位置能不能也依靠[L+K-1]已經不是本次要考慮的問題了，本次隻考慮能否讓[L]依靠其他的位置進而獲得免刷。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
const int maxn = 300005;
const int mod =1e9+7;
int n,m;
int dp[500][500];
int a[500];
int main()
{
int i,j,k,t;
int c,K;
while(scanf("%d%d%d",&n,&c,&K)!=EOF)
{
memset(dp,0,sizeof(dp));
for(i=1; i<=n; i++)
{
scanf("%d",&a[i]);
a[i+n]=a[i]; //環形開二倍
}
for(i=1; i<=2*n; i++)
for(j=i; j<=2*n; j++)
dp[i][j]=j-i+1; //起初設一塊石頭一種顔色
for(i=2*n-1; i>0; i--)//dp預處理出從每個點開始塗色的最優方案
for(j=i+1; j<=2*n; j++)
{
dp[i][j]=dp[i+1][j]+1;//位置i要塗色，先把它預置好，再去求是否是最優的
for(k=i+1; k<=j; k++)
{
if(a[i]==a[k]&&k-i+1<=K)//i,k最終顔色相同，如果i-k區間在給定一次刷的最大區間内，那麼我們就可以一次刷好
{
dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);//即dp[i+1][j]+1,與dp[i+1][k]+dp[k+1][j]的較量
}
}
}
int ans=INF;
for(i=1;i<=n;i++){//枚舉起點找dp最小值
ans=min(ans,dp[i][i+n-1]);
}
printf("%d\n",ans);
}
return 0;
}