NC19997. [HAOI2016]字符合并
描述
输入描述
第一行两个整数n，k。接下来一行长度为n的01串，表示初始串。接下来2^k行，每行一个字符ci和一个整数wi，ci 表示长度为k的01串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符,wi表示对应的第i种方案对应获得的分数。1 ≤ n ≤ 300,0 ≤ ci ≤ 1,wi ≥ 1, k ≤ 8
输出描述
输出一个整数表示答案
示例1
输入:
3 2 101 1 10 1 10 0 20 1 30
输出:
40
C++(g++ 7.5.0) 解法, 执行用时: 206ms, 内存消耗: 186904K, 提交时间: 2022-08-02 22:33:03
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e2+5,M=(1<<8);
char s[N];
ll w[M],c[M],g[2];
ll f[N][N][M];//从l到r合并成v的最大价值是多少.
int main()
{
int n,k;
scanf("%d%d",&n,&k);
scanf("%s",s+1);
for(int i=0;i<(1<<k);i++)
scanf("%lld%lld",&c[i],&w[i]);
memset(f,-0x3f,sizeof f);
ll inf=-(0x3f3f3f3f);
for(int i=1;i<=n;i++) f[i][i][s[i]-'0']=0;
for(int len=2;len<=n;len++)
{
for(int l=1;l<=n-len+1;l++)
{
int r=l+len-1;
int x=(len-1)%(k-1);
if(x==0) x=k-1;
for(int mid=r-1;mid>=l;mid-=(k-1))
{
for(int s=0;s<(1<<x);s++)
{
f[l][r][s<<1]=max(f[l][r][s<<1],f[l][mid][s]+f[mid+1][r][0]);
f[l][r][s<<1|1]=max(f[l][r][s<<1|1],f[l][mid][s]+f[mid+1][r][1]);
}
}
if(x==k-1)
{
g[0]=g[1]=inf;
for(int i=0;i<(1<<k);i++) g[c[i]]=max(g[c[i]],f[l][r][i]+w[i]);
f[l][r][0]=g[0],f[l][r][1]=g[1];
}
}
}
ll ans=inf;
for(int i=0;i<(1<<k);i++)
ans=max(ans,f[1][n][i]);
printf("%lld\n",ans);
return 0;
}
C++ 解法, 执行用时: 803ms, 内存消耗: 226084K, 提交时间: 2022-05-28 14:35:17
#include <bits/stdc++.h>
using namespace std;
int n,m,a[310],c[300],w[300];
long long f[310][310][300];
char S[310];
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",S+1);
for (int i=1;i<=n;i++)
a[i]=int(S[i]-48);
for (int i=0;i<(1<<m);i++)
scanf("%d%d",&c[i],&w[i]);
memset(f,-10,sizeof(f));
for (int i=1;i<=n;i++) f[i][i][a[i]]=0;
for (int len=2;len<=n;len++)
for (int l=1;l<=n-len+1;l++) {
int r=len+l-1;
for (int s=0;s<(1<<m);s++)
for (int k=r;k>l;k-=(m-1))
f[l][r][s]=max(f[l][r][s],f[l][k-1][s>>1]+f[k][r][s&1]);
if ((len-1)%(m-1)==0) {
long long g[2];
g[0]=g[1]=-1e12;
for (int s=0;s<(1<<m);s++)
g[c[s]]=max(g[c[s]],f[l][r][s]+w[s]);
f[l][r][0]=g[0];f[l][r][1]=g[1];
}
}
long long ans=0;
for (int i=0;i<(1<<m);i++)
ans=max(ans,f[1][n][i]);
cout<<ans;
return 0;
}