P4158[SCOI2009]粉刷匠
2024-09-06 00:33:51
题目描述
windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。
windy每次粉刷,只能选择一条木板上一段连续的格子,然后涂上一种颜色。 每个格子最多只能被粉刷一次。
如果windy只能粉刷 T 次,他最多能正确粉刷多少格子?
一个格子如果未被粉刷或者被粉刷错颜色,就算错误粉刷。
输入输出格式
输入格式:
第一行包含三个整数,N M T。
接下来有N行,每行一个长度为M的字符串,'0'表示红色,'1'表示蓝色。
输出格式:
包含一个整数,最多能正确粉刷的格子数。
代码
\(f[i][j]\)的数组来表示前i条木板粉刷j次的情况下能正确粉刷的最大格子数
\(g[i][j][k]\)来表示第i条木板上粉刷j次涂了前k个格子的情况下能正确粉刷的最大格
\(sum[i][j]\)数组来记录第i木板区间j前的蓝色格子数,红色格子:区间长度减去蓝色格子
dp方程:
\(g[i][j][k]=max(g[i][j][k],g[i][j-1][q]+max(sum[i][k]-sum[i][q],k-q-sum[i][k]+sum[i][q]));\)
\(f[i][j]=max(f[i][j],f[i-1][j-k]+g[i][k][m]);\)
#include<bits/stdc++.h>
using namespace std;
int n,m,t;
const int maxn=50+5,maxm=2500+5;
int f[maxn][maxm];
int g[maxn][maxm][maxn];
int sum [maxn][maxn];
int main()
{
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int a;
scanf("%1d",&a);
sum[i][j]=sum[i][j-1];
if(a==1)sum[i][j]++;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=m;k++)
for(int l=j-1;l<k;l++)
g[i][j][k]=max(g[i][j][k],g[i][j-1][l]+max(sum[i][k]-sum[i][l],k-l-sum[i][k]+sum[i][l]));
for(int i=1;i<=n;i++)
for(int j=1;j<=t;j++)
for(int k=0;k<=min(j,m);k++)
f[i][j]=max(f[i][j],f[i-1][j-k]+g[i][k][m]);
int ans=0;
for(int i=0;i<=t;i++)
ans=max(ans,f[n][i]);
printf("%d",ans);
return 0;
}
最新文章
- C语言学习003:Hello 指针
- 给深度学习入门者的Python快速教程 - numpy和Matplotlib篇
- IDEA集成MAVEN 报错
- 在不借助其他工具的情况下破解Windows开机密码
- 用Python作GIS之二:STARS开发环境配置
- 14.5.3 Locks Set by Different SQL Statements in InnoDB
- Windows 服务 Error 14001
- Fedora25和win10双系统安装及使问题汇总
- 『转载』从内存资源中加载C++程序集:CMemLoadDll
- Ajax+jquery+jaso传输数据
- Vue基础之内部指令(上)
- cocos2dx 3.x 修改NDK_ROOT、ANDROID_SDK_ROOT、ANT_ROOT路径
- Spring中 @Autowired标签与 @Resource标签 的区别
- asp.net 逻辑操作符与(&;&;),或(||),非(!)
- 十大高明的Google搜索技巧
- win10常用命令和设置总结
- HashSet remove()
- cad2018卸载/安装失败/如何彻底卸载清除干净cad2018注册表和文件的方法
- MVC的多页面后台管理系统
- sql server中批量插入与更新两种解决方案分享(存储过程)