poj2978——Colored stones

44424742

dp的解法总是那么给力，而我却仍不给力！！！为什么？
......
不多说，继续dp！
#include<iostream>#include<cstdio>using namespace std;const int pow[6]={1,2,4,8,16,32};int m,k,x[105];int dp[105][35][5];int main(){int s,i,c;while(cin>>m>>k&&m!=0&&k!=0){for(i=1;i<=m;i++){cin>>x[i];x[i]--;}for(s=0;s<pow[k];s++){for(c=0;c<k;c++)dp[0][s][c]=0;//初始化}for(i=1;i<=m;i++){int t=x[i];for(s=pow[k]-1;s>=0;s--){for(c=0;c<k;c++)dp[i][s][c]=dp[i-1][s][c];if((s&pow[t])!=0)//不属于s集合,此处的&用得很巧妙！！！dp[i][s][t]=dp[i-1][s][t]+1;else {int ss=s+pow[t];for(c=0;c<k;c++){if(dp[i][ss][t]<dp[i-1][s][c]+1)dp[i][ss][t]=dp[i-1][s][c]+1;}}}}int max=0;for(s=0;s<pow[k];s++){for(c=0;c<k;c++)if(max<dp[m][s][c])max=dp[m][s][c];}cout<<(m-max)<<endl;}return 0;}