【P1947】笨笨当粉刷匠（DP+前缀和）

这个题乍一看觉得挺简单的，事实上却完全不是。首先，这个题看上去无脑直接刷就可以然而因为刷的次数远远大于木板的个数所以不行，然后开始考虑DP，自己一开始是这么想的，如果用f[t][i][j]表示刷t次时，前i块板子刷到第j个最大值是多少，然后前缀和优化了一小下，勉强打出了二逼DP，然后90，之后从网上科普了一下，发现这样如果有一种中间有一整块不用涂的木板，那么就会崩掉。如讨论里的那一个90，是同一个错因。

之后换用了思路，首先还是前缀和对0和1的计算，然后算出对于第i块木板，涂到第j格子时，涂了k次能有的最大的价值，然后再用一个数组储存第i块木板涂j次的最优解，f表示前i块，涂j次的最优解，不难得出结果。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

#define re register

#define ll long long

using namespace std;

int f[][],t,r,n,m ,c[][][],v[][],ans,g[][][];

string s;

int main()

{

    cin>>n>>m>>t;

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

    {

        cin>>s;

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

        {

            c[i][j][]=c[i][j-][];

            c[i][j][]=c[i][j-][];

            c[i][j][s[j-]-'']++;//前缀和的计算。

        }

    }

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

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

      for(re int k=;k<=m;k++)

       for(re int l=;l<j;l++)

       {

           g[i][j][k]=max(g[i][j][k],g[i][l][k-]+max(c[i][j][]-c[i][l][],c[i][j][]-c[i][l][]));//以这个数组储存第i块j格子涂k次的最大值。

       }

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

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

      for(re int k=;k<=m;k++)

      {

          v[i][j]=max(v[i][j],g[i][k][j]);//这个数组储存第i块j次的。。

      }

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

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

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

    f[i][j]=max(f[i][j],f[i-][j-k]+v[i][k]);//dp数组求解。

    cout<<f[n][t];

}

巴特西

【P1947】笨笨当粉刷匠（DP+前缀和）

最新文章

热门文章