PKU 2978 Colored stones
http://poj.org/problem?id=2978
k種類の石がm個並べられている。
このm個の石からいくつかの石を取り除いていて、同じ種類の石が他の種類の石に分断されないような状態にしたい。
取り除かなければならない最低の石の個数を求めろというような問題。
dp[その石までに至るまでに出現した石の種類の集合][i個目の石]
=i個目の石を含むときに取り除かなくて良い石の最大の数。
みたいな感じでdpしました。
最高でもm-1個までしか取り除かないということを見落としていたり、変なことしてて2WA。
int dp[1<<5][100]; int in[100]; main(){ int m,k; while(cin>>m>>k,m){ memset(dp,0,sizeof(dp)); rep(i,m){ cin>>in[i]; --in[i]; dp[1<<in[i]][i]=1; } int ans=1; rep(i,m){ rep(j,i){ rep(l,1<<k){ if(in[j]!=in[i] && (l&(1<<in[i])))continue; ans=max(dp[l|1<<in[i]][i]=max(dp[l|1<<in[i]][i],dp[l][j]+1),ans); } } } cout<<m-ans<<endl; } }