bzoj1296[SCOI2009]粉刷匠

忘是亡心i 2021-12-24 19:37 242阅读 0赞

[bzoj1296\[SCOI2009\]粉刷匠][bzoj1296_SCOI2009]

题意：

粉刷N条木板，每条木板M 个格子，每个格子要被刷成红色或蓝色。每次只能选择一条木板上一段连续的格子涂上一种颜色。 每个格子最多只能被粉刷一次。 如果只能粉刷 T 次，求最多能正确粉刷的格子数。未被粉刷或者颜色错的格子算错误粉刷。

题解：

非常容易想的DP，但是我竟然调了0.5h+一个中午，不是一般的弱啊~~首先f\[i\]\[j\]\[k\]表示现在考虑第i行第j列，正在第k次粉刷，转移就考虑不粉刷跳到f\[i\]\[j+1\]\[k\]或粉刷x格跳到f\[i\]\[j+x\]\[k+1\]+max(红色j+1到j+x,蓝色j+1到j+x)。我主要错在几个方面：一是奇怪的打错；二是当j==m时，如果不涂往下一行跳转，j要变成0而不是1，因为是从j+1开始涂的；三是dp数组里因为有一个“正在第k次粉刷”，所以第三维要开到2500而不是50。错得好傻逼啊QAQ

代码：

1 #include <cstdio>
     2 #include <cstring>
     3 #include <algorithm>
     4 #include <cctype>
     5 #define inc(i,j,k) for(int i=j;i<=k;i++)
     6 using namespace std;
     7 
     8 int n,m,k; int w[60][60],b[60][60],f[60][60][3000]; char s[60];
     9 int dfs(int x,int y,int z){
    10     if(x==n+1||z==k+1)return 0; if(f[x][y][z]!=-1)return f[x][y][z];
    11     f[x][y][z]=0; f[x][y][z]=max(f[x][y][z],dfs(y==m?x+1:x,y==m?0:y+1,z));
    12     inc(i,y+1,m)
    13     f[x][y][z]=max(f[x][y][z],dfs(x,i,z+1)+max(w[x][i]-w[x][y],b[x][i]-b[x][y]));
    14     return f[x][y][z];
    15 }
    16 int main(){
    17     scanf("%d%d%d",&n,&m,&k);
    18     inc(i,1,n){
    19         scanf("%s",s);
    20         inc(j,0,m-1)if(s[j]=='1')w[i][j+1]=w[i][j]+1,b[i][j+1]=b[i][j];
    21                     else b[i][j+1]=b[i][j]+1,w[i][j+1]=w[i][j];
    22     }
    23     memset(f,-1,sizeof(f)); printf("%d",dfs(1,0,1));
    24     return 0;
    25 }

20160427

转载于:https://www.cnblogs.com/YuanZiming/p/5689627.html

[bzoj1296_SCOI2009]: http://www.lydsy.com/JudgeOnline/problem.php?id=1296