B. Modulo Sum dp

https://codeforces.com/contest/577/problem/B

先读懂题意，substring 这个是子串说明不可以跳 subsequence这个是子序列可以跳

这个题目是一个dp，不过你需要先知道，如果n>m 那么就肯定可以，

接下来证明一下这个，如果n>m，那么设前 i 项的和为 s[i] ，因为s[i]%m取模之后肯定再0~m-1

因为n>m 由抽屉原理可得一定有存在 s[i]==s[j]，这个所以存在 s[i]-s[j]==0 这个就说明肯定有m的倍数

然后也容易得到如果有n==m 也是满足条件的，因为n==m要么存在s[i]==0要么就是有s[i]==s[j]

接下来说说这个dp ，

因为有上面一个分析，就可以把n的数据范围降下来到1e3

所以呢，就可以直接开数组 dp[1e3][1e3] 接下来就是转移方程，这个转移方程很好想就是这一个数选还是不选

转移方程有两种选法一个是刷表法和填表法

填表法就是枚举当前状态，从现在的往前面这里推

dp[i][j]=max(dp[i-1][j],dp[i-1][(j+m-a[i]%m)]) 当前这个j可以从之前的j直接推过来，也可以是加了a[i]%m的j推过来，如果是第二种，那么之前的应该要现在的减去a[i]%m

刷表法就是枚举之前的状态，从前面往后面推，这样子一般都会推出两种状态，所以这个一般都有两个转移方程

dp[i][j]=max(dp[i-1][j],dp[i-1][j]) 这个就是说不加这个a[i]%m

dp[i][(j+a[i]%m)%m]=max(dp[i-1][(j+a[i]%m)%m],dp[i-1][j]) 这个就是加了a[i]%m

#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  mod = 1e8;

const int maxn = 5e5 + ;

int dp[][];

int a[maxn];

int main()

{

    int n, m;

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

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

    {

        scanf("%d", &a[i]);

    }

    if(n>=m)

    {

        printf("YES\n");

        return ;

    }

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

    {

        dp[i][a[i] % m] = ;

        //printf("dpp[%d][%d]=%d\n", i, a[i] % m, dp[i][a[i] % m]);

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

        {

            if(j!=a[i]%m) dp[i][j] = max(dp[i - ][j], dp[i - ][(j + m - (a[i]%m))%m]);

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

        }

    }

    if (dp[n][]) printf("YES\n");

    else printf("NO\n");

    return ;

}

巴特西

B. Modulo Sum dp

最新文章

热门文章