C. Barcode dp

https://codeforces.com/problemset/problem/225/C

这个题目和之前一个题目很像 https://www.cnblogs.com/EchoZQN/p/10900373.html

只是这个数据范围更大一些，

不过刚开始我真的没有看出来。。。。

这个就是整列整列的处理，所以还是一样枚举当前的连续的j

dp[i][j][k] 这个k只有两个取值，一个是0，一个是1，0 代表白色，1代表黑色。

这个定义就是dp[i][j][0] 前面i个连续j个白色的列需要粉刷的最少的砖的数量。

另外一个同样，

所以按照之前的想法，很贱的就可以知道会有两种情况，一个是j==1 那就说明是之前的情况推过来的，因为之前的这个j不确定，

所以这里要枚举每一种情况。

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<queue>

#include<vector>

#define inf 0x3f3f3f3f

#define debug(x) cout<<"-----"<<" x = "<<x<<"-----"<<endl

using namespace std;

typedef long long ll;

const int maxn = 5e3 + ;

ll dp[][][];

char s[][];

int b[], w[];

int main()

{

    int n, m, x, y;

    scanf("%d%d%d%d", &n, &m, &x, &y);

    for (int i = ; i <= n; i++) scanf("%s", s[i] + );

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

    {

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

        {

            if (s[i][j] == '.') w[j]++;

            else b[j]++;

        }

    }

    memset(dp, inf, sizeof(dp));

    dp[][][] = b[];

    dp[][][] = w[];

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

    {

        for(int j=;j<=y&&j<=i;j++)

        {

            if(j!=)

            {

                dp[i][j][] = dp[i-][j-][] + b[i];

                dp[i][j][] = dp[i-][j-][] + w[i];

            }

            else

            {

                for(int k=x;k<=y;k++)

                {

                    dp[i][j][] = min(dp[i][j][], dp[i-][k][] + b[i]);

                    dp[i][j][] = min(dp[i][j][], dp[i-][k][] + w[i]);

                }

            }

            // printf("dp[%d][%d][0]=%lld\n", i, j, dp[i][j][0]);

            // printf("dp[%d][%d][1]=%lld\n", i, j, dp[i][j][1]);

        }

    }

    ll ans = inf;

    for(int i=x;i<=y;i++)

    {

        ans = min(ans, dp[m][i][]);

        ans = min(ans, dp[m][i][]);

    }

    printf("%lld\n", ans);

    return ;

}

巴特西

C. Barcode dp

最新文章

热门文章