bzoj1296: [SCOI2009]粉刷匠(DP)
2024-08-31 14:09:31
1296: [SCOI2009]粉刷匠
题目:传送门
题解:
DP新姿势:dp套dp
我们先单独处理每个串,然后再放到全局更新:
f[i][k]表示当前串枚举到第i个位置,用了k次机会
F[i][j]则表示总答案
代码:
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,t;
int f[][];
int F[][];
char st[];int a[];
int main()
{
scanf("%d%d%d",&n,&m,&t);getchar();
memset(F,,sizeof(F));
for(int i=;i<=n;i++)
{
scanf("%s",st+);
a[]=;for(int j=;j<=m;j++)a[j]=a[j-]+st[j]-'';
memset(f,,sizeof(f));
for(int j=;j<=m;j++)
for(int k=;k<=min(j,t);k++)
for(int l=;l<=j;l++)
{
int s=a[j]-a[l-];
f[j][k]=max(f[j][k],f[l-][k-]+max(s,(j-l+)-s));
}
for(int j=;j<=t;j++)
for(int k=;k<=min(m,j);k++)
F[i][j]=max(F[i][j],F[i-][j-k]+f[m][k]);
}
int ans=1e-;
for(int i=;i<=t;i++)ans=max(ans,F[n][i]);
printf("%d\n",ans);
return ;
}
最新文章
- [原创]Win7、Win8、Win10始终以管理员身份运行程序。
- Java_关于App class loader的总结
- Hive简单优化;workflow调试
- xenserver+starwind架构布署
- Node.js中的事件
- 几个好用的截取字符串的php函数分享
- [selenium webdriver Java]常用api
- centos下如何用SMplayer播放WMV格式文件
- 掌握 ActionResult
- 三招搞挂Mysql(转)
- 2016年9月ccf
- JQuery中阻止事件冒泡的两种方式及其区别
- 天气情况(思维,dp思想)
- HTML5学习笔记<;一>;: 认识H5
- SynchronizedMap和ConcurrentHashMap 区别
- 下一个计划 : .NET/.NET Core应用性能管理系统
- 周末班:Python基础之函数进阶
- Crontab和sudo中无法使用TensorFlow ImportError libcublas.so.9.0
- [20180822]session_cached_cursors与子游标堆0.txt
- 数据库工具类 JdbcUtils
热门文章
- java内存管理之内存模型
- ajax 获取 json 数据乱码
- &;lt;pre&;gt;标签
- android官网被封掉了,仅仅好用这个站点进谷歌了!嘎嘎
- [Struts2] No result defined for action ... and result input &;amp; Invalid field value for field ...
- .Net MVC的学习(一)
- [codeforces 1037D] Valid BFS? 解题报告(验证bfs序,思维题)
- [Swift]数组(Array)最强解析
- localStorage、sessionStorage的区别
- HD-ACM算法专攻系列(8)——排序