bzoj3791作业*
2024-09-05 18:06:08
题意:
对一个01序列进行染色,每次能将一个区间染上色(可覆盖之前染的),共能染k次,求最大正确染色个数。n≤100000,m≤50。
题解:
结论:染k次最多能把序列分成2*k-1段。故dp即可:
f[i][j][0]=max(f[i+1][j+1][1]+a[i]==1,f[i+1][j][0]+a[i]==0)
f[i][j][1]=max(f[i+1][j][1]+a[i]==1,f[i+1][j+1][0]+a[i]==0)
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 110
#define INF 0x3fffffff
using namespace std; inline int read(){
char ch=getchar(); int f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return f*x;
}
int n,f[][maxn][],k,x,y; bool a[maxn*];
int main(){
n=read(); k=*read()-; inc(i,,n)a[i]=read(); x=; y=;
for(int i=n;i>=;i--){
f[x][k+][]=f[x][k+][]=-INF;
inc(j,,k){
f[y][j][]=max(f[x][j][]+(a[i]==),f[x][j+][]+(a[i]==));
f[y][j][]=max(f[x][j+][]+(a[i]==),f[x][j][]+(a[i]==));
}
swap(x,y);
}
printf("%d",max(f[x][][],f[x][][])); return ;
}
20160831
最新文章
- [No0000A9]实用word用法
- 微信小程序 关于底部导航设置
- iOS开发——UI进阶篇(六)键盘处理
- 使用JavaService.exe(amd64)发布java服务(jdk x64)
- http协议了解
- android如何实现开机自动启动Service或app
- XC软件管理器应用
- html5学习(一)--canvas画时钟
- EF4.0、4.3创建表达式树状动态查询总结
- readline与readlines不能同时使用
- 【解决方案】纯js动态克隆表一行元素
- Docker(九):Docker容器卷插件
- STL常用遍历算法for_each和transform的比较
- Android 常用的ORM框架详解
- VS2017 处理 Rdlc , microsoft report viewer 轻量级报表处理(WPF CS客户端版本)
- Linux常用命令汇总(一)
- IIS7常见错误及解决方法
- Python性能分析
- python基础知识小结-运维笔记
- Apache的项目列表
热门文章
- Codeforce Round #643 #645 #646 (Div2)
- linu使用x之sz下载和rz上传
- MySQL数据表中有自增长主键时如何插入数据
- matplotlib添加子图(拼图功能)
- vc6.0代码转vs2017相关问题
- xenomai内核解析之双核系统调用(一)
- .Net Core微服务入门全纪录(六)——EventBus-事件总线
- lin-cms-dotnetcore功能模块的设计
- viewerjs 在html打开图片或打开pdf文件使用案例
- windows虚拟机安装mac