[Haoi2016]字符合并 题解
2024-09-01 02:07:53
tijie
时间限制: 2 Sec 内存限制: 256 MB
题目描述
有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字
符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。
输入
第一行两个整数n，k。接下来一行长度为n的01串，表示初始串。接下来2k行，每行一个字符ci和一个整数wi，ci
表示长度为k的01串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符,wi表示对应的第i种方案对应
获得的分数。1<=n<=300,0<=ci<=1,wi>=1,k<=8
输出
输出一个整数表示答案
样例输入
3 2
101
1 10
1 10
0 20
1 30
样例输出
40
//第3行到第6行表示长度为2的4种01串合并方案。00->1,得10分，01->1得10分，10->0得20分，11->1得30分。
这道题当时是按照搜索或动归去做的，然而，想不出动归状态咋搞啊,于是乎，花了不到半个小时打了一个MLE的爆搜果断挂了，爆零。
其实正解真的是DP，只是状态蛮有意思的，这是一种区间动归的思想，因为他合并只是一段串合并，对左右两端的串无直接影响而n,k也不大，因此我们考虑一下状压，当时不是没想过这点，只是压什么，怎么压是个问题，我们自然是不可能去压全串的状态，但我们可以稍微算一下，区间动归所需的状态数组加上状压应是3维，300*300=90000，如果以一般数组大小（个人理解是1000000~20000000）的话大约还能压100~200左右，那么就是256——2^8了，2^8有什么实际意义呢8就是k的最小值，我们就可以根据这个信息猜到可能是要去压8位。
那么压8位的化状态数组就是f[301][301][1<<8]了，f[i][j][s]就表示从i到j之间进行字符串替换后成为s的状态所能得到的最大值，转移也就成为了区间动归套路，首先第一层循环一定是枚举区间长度，用小区间去维护大区间,第二层就是枚举左端点了，第三层也就是枚举中间值，由于还有状压，第四层就是枚举状态了，由于我们每次合并都是以k为长度，所以右端点不必挨个枚举，每次减去k-1即可。
然后如果len=k-1，说明该串可以被合并，我们就去找每个合法状态中转化为0或1中最大的两个，由于最终只能变化为0或1，这样无疑是正确的，然后，统计一下最优答案就好了。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
int n,k;
long long b[<<],c[<<];
long long f[][][<<];
char a[];
int main(){
// freopen("merge.in","r",stdin);
// freopen("merge.out","w",stdout);
memset(f,-0x7f,sizeof(f));
scanf("%d%d",&n,&k);
scanf("%s",a);
for(int i=;i<=n;i++)
{
f[i][i][a[i-]-'']=;
}
for(int i=;i<(<<k);i++)
{
scanf("%lld%lld",&b[i],&c[i]);
}
for(int l=;l<=n;l++)
{
for(int i=;i<=n-l+;i++)
{
int j=i+l-;
int len=j-i;
while(len>=k){
len-=k-;
}
for(int t=j;t>i;t-=k-)
{
for(int s=;s<(<<(len));s++)
{
if(f[i][t-][s]!=f[][][]&&f[t][j][]!=f[][][])
{
f[i][j][s<<]=max(f[i][j][s<<],f[i][t-][s]+f[t][j][]);
}
if(f[i][t-][s]!=f[][][]&&f[t][j][]!=f[][][])
{
f[i][j][s<<|]=max(f[i][j][s<<|],f[i][t-][s]+f[t][j][]);
}
}
}
if(len==k-)
{
long long g[];
g[]=g[]=f[][][];
for(int s=;s<(<<k);s++)
{
if(f[i][j][s]!=f[][][])
{
g[b[s]]=max(g[b[s]],f[i][j][s]+c[s]);
}
}
f[i][j][]=g[];
f[i][j][]=g[];
}
}
}
long long ans=f[][][];
for(int i=;i<(<<k);i++)
{
ans=max(ans,f[][n][i]);
}
printf("%lld\n",ans);
//while(1);
return ;
}
最新文章
- DataTable导出到Excel
- JSON.stringify 在OA差旅中转换为字符串传给后端，（使用from表单的形式）
- deep learning 练习 牛顿法完成逻辑回归
- 根据juery CSS点击一个标签弹出一个遮罩层的简单示例
- Windows 10 上强制Visual Studio以管理员身份运行
- windows下修改mysql用户名和密码
- vs2008 连接 VSS不提示输入密码
- 初识Tower Defense Toolkit
- html5 中常用的标签和属性
- java中常见的单例模式详解
- 基于visual Studio2013解决C语言竞赛题之0702函数设计
- python net-snmp 的使用
- JAVA_SE基础——61.字符串入门
- SpringMVC之数据传递一
- JavaScript进阶(十一)JsJava2.0版本
- GIL全局锁测试
- 【JavaScript】常用的数据类型的处理方式
- Hive数仓之快速入门（二）
- AndroidStudio连不上Android设备真机
- java.net.SocketException四大异常解决方案