Description

Input

Output

輸出一個整數表示答案

Sample Input

Sample Output

HINT

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

DP+神奇的記錄方式~

迷之復雜度……理論上應該是過不了的啊……究竟有多少狀態沒有搜到啊……

因為從小到大排序剛好是0~(1<<k)-1，所以直接用數組按順序記錄輸入的值就好了~

用f[i][j][z]表示區間[i,j]最終消成z（二進制記錄狀態）的最大得分，那么每次枚舉區間mid值（其中mid到j一定是k-1的倍數，否則狀態有誤），更新即可~

轉移方程：f[i][j][z<<1]=max(f[i][j][z<<1],f[i][mid-1][z]+f[mid][j][0]); f[i][j][z<<1|1]=max(f[i][j][z<<1|1],f[i][mid-1][z]+f[mid][j][1]);

注意：

（1）初始化中memset用128更新出來是負無窮，不是正值；

（2）題目中部分數據范圍缺失，點開“k<=8”里面有補充，w[i]是10^9，所以f[i][j][z]要開long long；

（3）題目中已有k，不能再用它來做變量（其實只有我自己會出現這樣的問題吧--）.

#include<cstdio>#include<cstring>#include<iostream>using namespace std;#define ll long longint n,s[301],c[1<<8],w[1<<8],k;ll f[301][301][1<<8],inf,ans;char ss[301];int read(){	int totnum=0;char ch=getchar();	while(ch<'0' || ch>'9') ch=getchar();	while(ch>='0' && ch<='9') {totnum=(totnum<<1)+(totnum<<3)+ch-'0';ch=getchar();}	return totnum;}int main(){	n=read();k=read();scanf("%s",ss+1);	for(int i=1;i<=n;i++) s[i]=ss[i]-'0';	for(int i=0;i<(1<<k);i++) c[i]=read(),w[i]=read();	memset(f,128,sizeof(f));inf=f[0][0][0];	for(int i=1;i<=n;i++) f[i][i][s[i]]=0;	for(int l=2;l<=n;l++)	  for(int i=1;i+l-1<=n;i++)	  {	  	int j=i+l-1,len=j-i;	  	while(len>k-1) len-=k-1;	  	for(int mid=j;mid>i;mid-=k-1)	  	  for(int z=0;z<(1<<len);z++)	  	    if(f[i][mid-1][z]!=inf)	  	    {	  	    	if(f[mid][j][0]!=inf) f[i][j][z<<1]=max(f[i][j][z<<1],f[i][mid-1][z]+f[mid][j][0]);	  	    	if(f[mid][j][1]!=inf) f[i][j][z<<1|1]=max(f[i][j][z<<1|1],f[i][mid-1][z]+f[mid][j][1]);	  	    }	  	if(len==k-1)	  	{	  		ll g[2];g[0]=g[1]=inf;	  		for(int z=0;z<(1<<k);z++)	  		  if(f[i][j][z]!=inf) g[c[z]]=max(g[c[z]],f[i][j][z]+w[z]);	  		f[i][j][0]=g[0];f[i][j][1]=g[1];	  	}	  }	for(int i=0;i<(1<<k);i++) ans=max(ans,f[1][n][i]);	PRintf("%lld/n",ans);	return 0; }