「HAOI2016」字符合并
题意:
有一个长度为\(n\)的\(01\)串,你可以每次将相邻的\(k\)个字符合并,得到一个新的字符并获得一定分数。得到的新字符和分数由这\(k\)个字符确定。你需要求出你能获得的最大分数。(\(n\le 300,k\leq8\))
题解:
关键是要想到区间dp。记\(f[i][j][s]\),表示区间\([i,j]\),合并后状态为\(s\)的最大值。注意到长度模\(k\)余\(1\)的区间都可合并成一个字符,那么转移枚举的中点每次可以跳动\(k-1\)步,\(s\)的取值为\(2\)的\((j-i) \ mod (k-1)\)次幂,当\(s\)是\(k-1\)的倍数时加上合并的贡献就可以了。
#include<bits/stdc++.h>
#define fo(i,l,r) for(ll i=l;i<=r;i++)
#define of(i,l,r) for(ll i=l;i>=r;i--)
#define fe(i,u) for(ll i=head[u];i;i=e[i].next)
#define el putchar('\n')
#define ta putchar(' ')
using namespace std;
typedef long long ll;
inline void open(const char *s)
{
#ifndef ONLINE_JUDGE
char str[20];
sprintf(str,"%s.in",s);
freopen(str,"r",stdin);
// sprintf(str,"%s.out",s);
// freopen(str,"w",stdout);
#endif
}
inline ll rd()
{
static ll x,f;
x=0;f=1;
char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return f>0?x:-x;
}
const int N=310;
int n,m;
char s[N];
ll a[N],b[N],f[N][N][256];
int main()
{open("hh");
n=rd();m=rd();
scanf("%s",s+1);
ll Max=(1<<m)-1;
fo(i,0,Max)a[i]=rd(),b[i]=rd();
memset(f,-0x3f,sizeof f);
of(i,n,1)fo(j,i,n){
if(i==j){f[i][j][s[i]-48]=0;continue;}
ll L=j-i;L%=(m-1);if(!L)L+=(m-1);
for(ll mid=j;mid>i;mid-=m-1)fo(s,0,(1<<L)-1){
f[i][j][s<<1]=max(f[i][j][s<<1],f[i][mid-1][s]+f[mid][j][0]);
f[i][j][s<<1|1]=max(f[i][j][s<<1|1],f[i][mid-1][s]+f[mid][j][1]);
}
if(L==m-1){
static ll g[2];g[0]=g[1]=f[0][0][0];
fo(s,0,(1<<m)-1)g[a[s]]=max(g[a[s]],f[i][j][s]+b[s]);
f[i][j][0]=g[0];
f[i][j][1]=g[1];
}
}
ll ans=0;
fo(i,0,Max)ans=max(ans,f[1][n][i]);
cout<<ans<<endl;
return 0;
}