P1136 迎接仪式
2024-09-30 00:27:20
$O(n^{2}k)$:$f[i][k]$表示到第$i$个字符为止,交换$k$次,得到的最多子串数
那么枚举位置$j$,状态可以从$f[j][k-1]+1$转移过来
$O(nk^{2})$:$f[i][j][k]$表示到第$i$个字符为止,$j$个$“j”$字符转换成$“z”$,$k$个$“z”$字符转换成$“j”$的价值。
枚举4种状态:$“zj”,"zz","jj","jz"$,分别转移即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
using namespace std;
int max(int &a,int &b){return a>b?a:b;}
int n,k,ans,f[][][];
char a[];
int main(){
scanf("%d%d",&n,&k);
scanf("%s",a+);
memset(f,,sizeof(f));//初始化极小值
f[][][]=f[][][]=f[][a[]=='j'][a[]=='z']=;
for(re int i=;i<=n;++i)
for(re int j=;j<=k;++j)
for(re int u=;u<=k;++u){
f[i][j][u]=f[i-][j][u];
if(a[i-]=='j'&&a[i]=='z') f[i][j][u]=max(f[i][j][u],f[i-][j][u]+);
if(j&&a[i-]=='j'&&a[i]=='j') f[i][j][u]=max(f[i][j][u],f[i-][j-][u]+);
if(u&&a[i-]=='z'&&a[i]=='z') f[i][j][u]=max(f[i][j][u],f[i-][j][u-]+);
if(j&&u&&a[i-]=='z'&&a[i]=='j') f[i][j][u]=max(f[i][j][u],f[i-][j-][u-]+);
}
for(re int i=;i<=k;++i) ans=max(ans,f[n][i][i]);//交换就是'j','z'修改的个数相同
printf("%d",ans);
return ;
}
最新文章
- HTML和CSS经典布局5
- php配置
- [虚拟化/云][全栈demo] 为qemu增加一个PCI的watchdog外设(一)
- VS 2017 Git failed with a fatal error的解决办法
- servlet以及HTML中路径问题
- 在不用Promise的情况下如何控制异步请求?
- 使用IDEA配置Maven + SpringMVC + Mybatis 【一步一步踩坑详细配置完成】
- php 使用Glob() 查找文件技巧
- PHP 内置函数fgets读取文件
- node-rsa
- java NIO Buffer 详解(1)
- wkhtmltopdf错误解决办法
- Go Revel - Controllers(控制器)
- 告知你不为人知的UDP-连接性和负载均衡
- 数据网格和树-EasyUI Datagrid 数据网格、EasyUI Propertygrid 属性网格、EasyUI Tree 树、EasyUI Treegrid 树形网格
- PostgreSQL时间格式及相关函数实践
- Android学习笔记_15_网络通信之文件断点下载
- Linux系统安装jdk后出现无法执行binary 文件的错误解决
- git 因线上分支名重复导致无法拉取代码
- [Machine Learning with Python] Data Preparation by Pandas and Scikit-Learn
热门文章
- 使用vue-cli结合express获取mongodb里面的数据
- 《C#高级编程》学习笔记------抗变和协变
- 【BZOJ5110】[CodePlus2017]Yazid 的新生舞会 线段树
- 【BZOJ2661】[BeiJing wc2012]连连看 最大费用流
- 如何判断SharedPreferences 记录存在
- log file sync 事件(转)
- ajax跨域终极解决办法!
- Apache配置虚拟主机httpd-vhosts.conf
- pymysql executemany
- python tensorflow keras