「NOIP模拟赛」笨笨当粉刷匠
笨笨太好玩了，农田荒芜了，彩奖用光了，笨笨只好到处找工作，笨笨找到了一份粉刷匠的工作。笨笨有n条木板需要被粉刷。每条木板被分成m个格子，每个格子要被刷成红色或蓝色。笨笨每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色，已知每个格子最多只能被粉刷一次。
如果笨笨只能粉刷t次，他最多能正确粉刷多少格子。
一个格子如果未被粉刷或被粉刷成错误颜色，就算粉刷错误。
「输入格式」
第一行三个数n，m，t；
接下来n行，每行一个长度为m的字符“0”表示红色，”1″表示蓝色。
「输出格式」
一个整数，最多能正确粉刷的格子数。
Sample input
3 6 3
111111
000000
001100
Sample output
16
100％数据范围满足1≤n，m≤50；0≤t≤2500。
bzoj粉刷匠。。。
但是发现bzoj数据水了。。。有可能某些木板一次也不粉刷
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #define inf 0x7fffffff #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,t,ans; int sum[55]; int f[55][55],dp[55][2505]; char s[60]; void pre() { //freopen("draw.in","r",stdin); //freopen("draw.out","w",stdout); scanf("%s",s+1); for(int i=1;i<=m;i++) sum[i]=sum[i-1]+(s[i]=='1'); for(int i=1;i<=m;i++) for(int x=1;x<=m;x++) { f[x][i]=0; for(int y=0;y<x;y++) { int tmp=sum[x]-sum[y]; f[x][i]=max(f[x][i],f[y][i-1]+max(tmp,x-y-tmp)); } } } int main() { n=read(),m=read(),t=read(); for(int i=1;i<=n;i++) { pre(); for(int j=1;j<=t;j++) { int tmp=min(m,j); for(int k=0;k<=tmp;k++) dp[i][j]=max(dp[i][j],dp[i-1][j-k]+f[m][k]); } } for(int i=1;i<=t;i++) ans=max(dp[n][i],ans); printf("%d",ans); return 0; } |
Subscribe
计数器 9675210
OI 课件=>
OI 课件=>