bzoj 1296: [SCOI2009]粉刷匠
2024-10-19 00:21:40
Description
windy有 N 条木板需要被粉刷。 每条木板被分为 M 个格子。 每个格子要被刷成红色或蓝色。 windy每次粉刷,只能选择一条木板上一段连续的格子,然后涂上一种颜色。 每个格子最多只能被粉刷一次。 如果windy只能粉刷 T 次,他最多能正确粉刷多少格子? 一个格子如果未被粉刷或者被粉刷错颜色,就算错误粉刷。
Input
输入文件paint.in第一行包含三个整数,N M T。 接下来有N行,每行一个长度为M的字符串,'0'表示红色,'1'表示蓝色。
Output
输出文件paint.out包含一个整数,最多能正确粉刷的格子数。
Sample Input
3 6 3
111111
000000
001100
111111
000000
001100
Sample Output
16
HINT
30%的数据,满足 1 <= N,M <= 10 ; 0 <= T <= 100 。 100%的数据,满足 1 <= N,M <= 50 ; 0 <= T <= 2500 。
Source
http://www.lydsy.com/JudgeOnline/problem.php?id=1296
线性dp
#include <stdio.h>
#define MAXN 3000
int f[MAXN][MAXN],sum[MAXN];
int dp[MAXN][MAXN];
char in[MAXN];
int max(int a,int b)
{
if(a>b) return a;
return b;
}
int min(int a,int b)
{
if(a<b) return a;
return b;
}
int main()
{
int k,i,j,n,m,t,l,ans=-;
scanf("%d%d%d",&n,&m,&t);
for(k=;k<=n;k++)
{
scanf("%s",in+);
for(i=;i<=m;i++)
sum[i]=sum[i-]+(in[i]=='');
for(i=;i<=m;i++)
for(j=;j<=m;j++)
{
f[j][i]=;
for(l=;l<j;l++)
{
int cnt=sum[j]-sum[l];
f[j][i]=max(f[j][i],f[l][i-]+max(cnt,j-l-cnt));
}
}
for(i=;i<=t;i++)
{
int cnt=min(m,i);
for(j=;j<=cnt;j++)
dp[k][i]=max(dp[k][i],dp[k-][i-j]+f[m][j]);
}
}
for(i=;i<=t;i++)
ans=max(ans,dp[n][i]);
printf("%d\n",ans);
return ;
}
最新文章
- Java Web学习路线
- Which is the best opencv or matlab for image processing?
- 用PHP实现定时器功能
- Java基本开发环境搭建
- oracle顺序控制语句goto、null和分页过程中输入输出存储、java程序的调用过程
- node c#
- DTO学习系列之AutoMapper(五)----当EntityFramework爱上AutoMapper
- 转: HTML5新特性之Mutation Observer
- 玩转Web之servlet(四)---B/S是如何使用http协议完成通信过程的
- 通过配置的方式Autofac(1)
- Spring+struts+ibatis(一)环境准备工作
- 设计模式原则(2)--Liskov Substitution Principle(LSP)--里氏替换原则
- c++ 之模板进阶
- mysql 定期删除表中无用数据
- java导出excel模板数据
- MATLAB运行edge函数闪退
- Unity NavMesh导航网格 初级教程
- How to chain a command after sudo su?
- mac删除python
- 【一题多解】Python 字符串逆序