你发现染 $k$ 次最多会将这个序列分成 $2k-1$ 段,然后任何 $2k-1$ 段以内的方案一定能被构建出来,所以直接 dp 就好了

#include <bits/stdc++.h>
#define N 100004
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int A[N],f[N][104][2];
int main()
{
int n,k,i,j;
// setIO("input");
scanf("%d%d",&n,&k);
k=k*2-1;
for(i=1;i<=n;++i) scanf("%d",&A[i]);
int ans=0,p;
for(i=1;i<=n;++i)
{
for(j=1;j<=k;++j)
{
if(A[i]==0)
{
f[i][j][0]=max(f[i-1][j-1][1]+1, f[i-1][j][0]+1);
f[i][j][1]=f[i-1][j][1];
}
else
{
f[i][j][0]=f[i-1][j][0];
f[i][j][1]=max(f[i-1][j-1][0]+1, f[i-1][j][1]+1);
}
ans=max(ans, f[i][j][0]);
ans=max(ans, f[i][j][1]);
}
}
printf("%d\n",ans);
return 0;
}

  

最新文章

  1. List转换成json格式字符串,json格式字符串转换成list
  2. DP~数塔(hrbustoj1004)
  3. 2016年10月12日--string、Math类、Random随机数、DateTime、异常保护
  4. Eclipse中使用Junit编写测试用例
  5. centos7.0 没有netstat 和 ifconfig命令问题
  6. cdoj 1256 昊昊爱运动 预处理/前缀和
  7. ruby 删除文件夹(包括文件夹中的文件夹和文件)
  8. 由于问题引起信号ORA-27154无法启动数据库
  9. Hadoop权威指南:压缩
  10. rabbitMQ教程(二)一篇文章看懂rabbitMQ
  11. Spring Boot 2.x基础教程:工程结构推荐
  12. jmeter学习笔记--概述
  13. ionic 解决APP安装到android上 状态栏显示黑色
  14. java_lambda表达式
  15. Codechef MGCHGYM Misha and Gym 容斥、背包、Splay
  16. 生产者消费者模式 php 【转】
  17. 005_关于HTTP协议中的保持连接
  18. 2.12 C++ explicit关键字详解
  19. vue中使用animate.css
  20. qmake使用方法(自动生成Makefile文件)

热门文章

  1. 1204: 移位运算(C)
  2. oj上的测试点信息
  3. MogileFS表说明
  4. (转)js-分享功能(qq,微信,微博)
  5. RDS for MySQL 逻辑备份文件恢复到自建数据库
  6. 使用github经验
  7. SQL Server系统函数:字符串函数
  8. vue 集成jTopo 处理方法
  9. c++-01--迭代器
  10. 超详细Nginx的安装和配置教程