首页 > 代码库 > BZOJ1296: [SCOI2009]粉刷匠

BZOJ1296: [SCOI2009]粉刷匠

2024-07-20 01:45:36   222人阅读

1296: [SCOI2009]粉刷匠

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 844  Solved: 486
[Submit][Status]

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

Sample Output

16

HINT

30%的数据，满足 1 <= N,M <= 10 ； 0 <= T <= 100 。
100%的数据，满足 1 <= N,M <= 50 ； 0 <= T <= 2500 。

Source

Day2

题解：
数据范围这么小，怎么着都可以。。。
因为每一行是独立的，所以对于每一行我们DP出涂几次最多可以涂正确多少个格子
具体地说可以用 b[i][j]表示 涂到i 涂了 j 次 最多涂对多少个格子来转移
然后我们需要把这t 次 分到每一行中
这就成了一个分组背包问题了，再次DP之
代码：
 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 50+1014 #define maxm 500+10015 #define maxt 2500+10016 #define eps 1e-1017 #define ll long long18 #define pa pair<int,int>19 using namespace std;20 inline int read()21 {22     int x=0,f=1;char ch=getchar();23     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}24     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}25     return x*f;26 }27 int n,m,t,a[maxn],b[maxn][maxn],f[maxt];28 inline bool cmp(int x,int y)29 {30     return x>y;31 }32 inline int calc(int x,int y)33 {34     int tt[2];tt[1]=0;tt[0]=0;35     for(int i=x;i<=y;i++)tt[a[i]]++;36     return max(tt[0],tt[1]);37 }38 int main()39 {40     freopen("input.txt","r",stdin);41     freopen("output.txt","w",stdout);42     n=read();m=read();t=read();43     f[0]=1;44     for(int i=1;i<=n;i++)45     {46      char ch=‘ ‘;47      while(ch<‘0‘||ch>‘1‘)ch=getchar();a[1]=ch==‘1‘?1:0;48      for(int j=2;j<=m;j++)ch=getchar(),a[j]=ch==‘1‘?1:0;49      memset(b,0,sizeof(b));50      for(int j=1;j<=m;j++)51       for(int k=1;k<=min(m,t);k++)52        for(int l=k-1;l<j;l++)53         b[j][k]=max(b[j][k],b[l][k-1]+calc(l+1,j));54      for(int j=t;j>=1;j--) 55       for(int k=1;k<=min(m,t);k++)56        if(f[j-k])f[j]=max(f[j],f[j-k]+b[m][k]);57     }58     printf("%d\n",f[t]-1);59     return 0;60 }
View Code

 看题解发现还有一个前缀和优化，可以每次转移达到O(1)，a[i]表示1..i有几个1就OK了，加上这个优化时间缩成了1/3.

代码：

 

 

BZOJ1296: [SCOI2009]粉刷匠


联系
我们