『字符合并 区间dp 状压dp』
2024-09-04 21:21:16
<更新提示>
<第一次更新>
<正文>
字符合并
Description
有一个长度为 n 的 01 串,你可以每次将相邻的 k 个字符合并,得到一个新的字符并获得一定分数。得到的新字符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。
Input Format
第一行两个整数n,k。接下来一行长度为n的01串,表示初始串。
接下来2^k行,每行一个字符ci和一个整数wi,ci表示长度为k的01串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符,wi表示对应的第i种方案对应获得的分数。
1<=n<=300,0<=ci<=1,wi>=1,k<=8
Output Format
输出一个整数表示答案
Sample Input
3 2
101
1 10
1 10
0 20
1 30
Sample Output
40
解析
首先,我们很容易想到区间\(dp\):\(f[l][r]\)代表合并区间\([l,r]\)的最大分数。但是这样记录状态好像不太好,因为区间合并后还会留下一些字符,这些字符还会产生一些价值。
如果考虑可以合并就合并的话,我们发现一个区间的剩余字符数不会超过\(k\)个,\(k\leq 8\)。
那就考虑状态压缩:\(f[l][r][S]\)代表合并区间\([l,r]\),得到字符集\(S\)的最大价值。然后我们就考虑用区间\(dp\)的框架来执行转移。首先,我们一定要枚举一个断点,然后合并两个区间。但是现在我们状态中还有一个\(S\),难道再枚举两个\(S_1,S_2\)来合并吗?
这样时间复杂度肯定是承受不了的。有一种更好的转移方式就是每次只考虑断点右边的区间合并成原区间状态\(S\)中的最后一个字符,这样同样可以做到更新不存在遗漏。
那么我们根据这样的方式转移即可:\(1.\) 执行通过子区间合并的转移。 \(2.\) 当区间长度可以合并时,执行计算合并贡献的转移。
\(Code:\)
#include <bits/stdc++.h>
using namespace std;
const int N = 302 , K = 8;
const long long INF = 0x3f3f3f3f;
int n,k,a[N],c[1<<K];
long long w[1<<K],f[N][N][1<<K];
inline void input(void)
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
scanf("%1d",&a[i]);
for (int i=0;i<1<<k;i++)
scanf("%d%lld",&c[i],&w[i]);
}
inline void DynamicProgram(void)
{
memset( f , 0xcf , 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,r;(r=l+len-1)<=n;l++)
{
int L = (len-1) % (k-1);
if ( L == 0 ) L = k-1;
for (int mid=r-1;mid>=l;mid-=k-1)
for (int S=0;S<1<<L;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 ( L == k-1 )
{
long long g[2] = {-INF,-INF};
for (int S=0;S<1<<k;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];
}
}
}
int main(void)
{
input();
DynamicProgram();
long long ans = -INF;
for (int S=0;S<1<<k;S++)
ans = max( ans , f[1][n][S] );
printf("%lld\n",ans);
return 0;
}
<后记>
最新文章
- php curl获取的数据不直接输出
- SwipeRefreshLayout下拉刷新简单用例
- Android组件---四大布局的属性详解
- Bootstrap系列 -- 22. 按钮详解
- 《Head First设计模式(中文版)》
- 百度地图Api 根据两个坐标点计算距离
- NYOJ 47过河问题
- 认识CSS样式
- 三个JS函数闭包(closure)例子
- hdu_2224_The shortest path(dp)
- 【LeetCode】125. Valid Palindrome
- iOS 电脑新装的系统, 使用sourceTree 创建本地仓库的时候, 总是提示, 无效路径
- Cocos2D:塔防游戏制作之旅(九)
- javase---string类介绍01
- 【题解】Luogu P5313 僕たちはひとつの光([Ynoi2012]D2T2)
- Code First 不自动生成数据库
- zabbix-3.0.4添加对windows 2008r2的监控
- SMP多核启动
- Java第三阶段学习(十三、会话技术、Cookie技术与Session技术)
- string int 类型转换