SCOI2009粉刷匠

2022-11-06 14:18:17

Description

windy有 N 条木板需要被粉刷。每条木板被分为 M 个格子。每个格子要被刷成红色或蓝色。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。每个格子最多只能被粉刷一次。如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。

Input

输入文件paint.in第一行包含三个整数，N M T。接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色。

Output

输出文件paint.out包含一个整数，最多能正确粉刷的格子数。

Solution

首先动规产生每块木板前几笔最多能正确粉刷多少个格子。再一次动规产生前几块木板刷几笔最多能正确粉刷多少格子，所以需要两次动规。

Code

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 using namespace std;

 int tot[],f[][],w[][],f2[][];

 char a[][];

 int main()

 {

     int n,m,t;

     cin>>n>>m>>t;

     for (int i=; i<=n; i++)

       for (int j=; j<=m; j++)

         cin>>a[i][j];

     int sum;

     for (int k=; k<=n; k++)

     {

       for (int i=; i<=m; i++)

         if (a[k][i]=='') tot[i]=tot[i-]+;

           else tot[i]=tot[i-];

       for (int i=; i<=m; i++)

         for (int j=; j<=m; j++)

         {

           f[j][i]=;

           for (int p=; p<=j-; p++)

           {

             sum=tot[j]-tot[p];

             f[j][i]=max(f[j][i],f[p][i-]+max(j-sum-p,sum));

           }

           for (int i=;i<=m;i++)

             w[k][i]=f[m][i];//w表示第k块木板涂i笔，f表示这块木板前m个格子（即整块）涂i笔

         }

     }

     for (int i=;i<=n;i++)

       for (int j=;j<=t;j++)

         for (int k=;k<=j;k++)

           if (k<=m) f2[i][j]=max(f2[i-][j-k]+w[i][k],f2[i][j]);

     cout<<f2[n][t]<<endl;

     return ;

 }

Source

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

码农公寓