bzoj4565【HAOI2016】字符合并
來源：程序員人生 發布時間：2016-07-05 14:23:08 閱讀次數：2828次
4565: [Haoi2016]字符合并
Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 102 Solved: 49
[Submit][Status][Discuss]
Description
有1個長度為 n 的 01 串，你可以每次將相鄰的 k 個字符合并，得到1個新的字符并取得1定分數。得到的新字
符和分數由這 k 個字符肯定。你需要求出你能取得的最大分數。
Input
第1行兩個整數n，k。接下來1行長度為n的01串，表示初始串。接下來2k行，每行1個字符ci和1個整數wi，ci
表示長度為k的01串聯成2進制后按從小到大順序得到的第i種合并方案得到的新字符,wi表示對應的第i種方案對應
取得的分數。1<=n<=300,0<=ci<=1,wi>=1,k<=8
Output
Sample Input
3 2
101
1 10
1 10
0 20
1 30
Sample Output
40
//第3行到第6行表示長度為2的4種01串合并方案。00->1,得10分，01->1得10分，10->0得20分，11->1得30分。
DP
f[i][j][0]和f[i][j][1]表示區間[i,j]合并為0或1的最大分數。
g[j][k]表示當前的i到j合并為k的最大分數。
然后是很麻煩的轉移，詳見程序。
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define N 300
using namespace std;
int n,m;
ll w[N],c[N],f[N][N][2],g[N][N],tmp[2],ans[N];
char s[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=⑴;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
n=read();m=read();
scanf("%s",s+1);
F(i,0,(1<<m)⑴) c[i]=read(),w[i]=read();
memset(f,⑴,sizeof(f));
F(i,1,n) f[i][i][s[i]-'0']=0;
D(i,n-m+1,1)
{
memset(g,⑴,sizeof(g));
int now=1;
g[i][0]=f[i][i][0];g[i][1]=f[i][i][1];
F(j,i+1,n)
{
F(x,0,(1<<now)⑴) if (g[j⑴][x]>=0) for(int k=j;k<=n;k+=m⑴)
{
if (f[j][k][0]>=0) g[k][x<<1]=max(g[k][x<<1],g[j⑴][x]+f[j][k][0]);
if (f[j][k][1]>=0) g[k][x<<1|1]=max(g[k][x<<1|1],g[j⑴][x]+f[j][k][1]);
}
now++;
if (now==m)
{
tmp[0]=tmp[1]=⑴;
F(x,0,(1<<m)⑴) if (g[j][x]>=0) tmp[c[x]]=max(tmp[c[x]],w[x]+g[j][x]);
f[i][j][0]=g[j][0]=tmp[0];
f[i][j][1]=g[j][1]=tmp[1];
now=1;
}
}
}
F(i,1,n) for(int j=i;j<=n;j+=m⑴) ans[j]=max(ans[j],ans[i⑴]+max(f[i][j][0],f[i][j][1]));
printf("%lld\n",ans[n]);
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
