[HAOI2016]字符合并
2022/6/26 23:26:04
本文主要是介绍[HAOI2016]字符合并,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
luogu 题面
题目大意
有一个长度为 \(n\) 的 \(01\) 串,你可以每次将相邻的 \(k\) 个字符合并,得到一个新的字符并获得一定分数。
得到的新字符和分数由这 \(k\) 个字符确定。你需要求出你能获得的最大分数。
题目分析
因为所有的分数都不存在负数,所以我们肯定要选到不能选,也就是直到整个 \(01\) 串的长度小于 \(k\) 为止。经过数学归纳法,我们也能够发现:当原串的长度为 \(l\) 时,最后剩下的长度为 \((l-1)\bmod(k-1)+1\)。
可以通过计算得到当前串剩下的长度而进行枚举。
令 \(dp[l][r][i]\) 表示区间 \([l,r]\) 变成状态 \(i\) 的最大分数。
状态转移方程类似于石子合并,\(dp[l,r,s]=\max\{dp[l][k][s>>1]+dp[k+1][r][0/1]\}\)。
但要注意枚举断点时每次减去 \(k-1\)。因为我们状态转移中右边区间合并成一位,而只有长度为 \(a(k-1)+1\) 的区间才能合并成 \(1\) 位,故如此。并且枚举需要倒序枚举。
代码
// Problem: P3736 [HAOI2016]×Ö·ûºÏ²¢ // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P3736 // Memory Limit: 250 MB // Time Limit: 1000 ms // Date:2022-06-25 22:30 // // Powered by CP Editor (https://cpeditor.org) #include <iostream> #include <cstdio> #include <climits>//need "INT_MAX","INT_MIN" #include <cstring>//need "memset" #include <numeric> #include <algorithm> #include <cmath> #define int long long #define enter putchar(10) #define debug(c,que) std::cerr << #c << " = " << c << que #define cek(c) puts(c) #define blow(arr,st,ed,w) for(register int i = (st);i <= (ed); ++ i) std::cout << arr[i] << w; #define speed_up() std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0) #define mst(a,k) memset(a,k,sizeof(a)) #define stop return(0) const int mod = 1e9 + 7; inline int MOD(int x) { if(x < 0) x += mod; return x % mod; } namespace Newstd { char buf[1 << 21],*p1 = buf,*p2 = buf; inline int getc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1 << 21,stdin),p1 == p2) ? EOF : *p1 ++; } inline int read() { int ret = 0,f = 0;char ch = getc(); while (!isdigit(ch)) { if(ch == '-') f = 1; ch = getc(); } while (isdigit(ch)) { ret = (ret << 3) + (ret << 1) + ch - 48; ch = getc(); } return f ? -ret : ret; } inline double double_read() { long long ret = 0,w = 1,aft = 0,dot = 0,num = 0; char ch = getc(); while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getc(); } while (isdigit(ch) || ch == '.') { if (ch == '.') { dot = 1; } else if (dot == 0) { ret = (ret << 3) + (ret << 1) + ch - 48; } else { aft = (aft << 3) + (aft << 1) + ch - '0'; num ++; } ch = getc(); } return (pow(0.1,num) * aft + ret) * w; } inline void write(int x) { if(x < 0) { putchar('-'); x = -x; } if(x > 9) write(x / 10); putchar(x % 10 + '0'); } } using namespace Newstd; const int INF = 0x3f3f3f3f3f3f3f3f; const int N = 305,M = 8; int a[N],c[(1 << M) + 1],w[(1 << M) + 1],dp[N][N][(1 << M) + 1]; //dp[l][r][k]:[l,r] ±ä³É״̬ i µÄ×î´ó·ÖÊý int n,m; int32_t main(void) { scanf("%lld%lld",&n,&m); for (register int i = 1;i <= n; ++ i) scanf("%1lld",a + i); for (register int i = 0;i < (1 << m); ++ i) scanf("%lld%lld",c + i,w + i); mst(dp,-0x3f); for (register int i = 1;i <= n; ++ i) dp[i][i][a[i]] = 0; for (register int len = 2;len <= n; ++ len) { for (register int l = 1;l + len - 1 <= n; ++ l) { int r = l + len - 1; int tmp = (len - 1) % (m - 1); if (!tmp) tmp = m - 1; for (register int k = r - 1;k >= l;k -= m - 1) { for (register int v = 0;v < (1 << tmp); ++ v) { dp[l][r][v << 1] = std::max(dp[l][r][v << 1],dp[l][k][v] + dp[k + 1][r][0]); dp[l][r][v << 1 | 1] = std::max(dp[l][r][v << 1 | 1],dp[l][k][v] + dp[k + 1][r][1]); } } if (tmp == m - 1) { int t1 = -INF,t2 = -INF; for (register int k = 0;k < (1 << m); ++ k) { if (c[k] == 0) t1 = std::max(t1,dp[l][r][k] + w[k]); else t2 = std::max(t2,dp[l][r][k] + w[k]); } dp[l][r][0] = t1,dp[l][r][1] = t2; } } } int res = -INF; for (register int i = 0;i < (1 << m); ++ i) { res = std::max(res,dp[1][n][i]); } printf("%lld\n",res); return 0; }
这篇关于[HAOI2016]字符合并的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-20测试人员都是画画大神,让我看看谁还不会用代码图?
- 2024-05-20年薪百万的程序员都在用的摸鱼方式……
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了