K序列（DP）

K序列

题目

给一个数组 a，长度为 n，若某个子序列中的和为 K 的倍数，那么这个序列被称为“K 序列”。对数组 a 求出最长的子序列的长度，满足这个序列是 K 序列。

输入一个n，k，接下来输入n个整数，表示A[1]~A[n] ,1<=n<=1e5,1<=a[i]<=1e9,1<=nK<=1e7。输出最长子序列的长度。

思路

又一道DP。

dp[i][j] : 表示前i个数中，对k取模余数为j的最长的子序列长度

dp[i][j] =max (dp[i-1][j],dp[i-1][(k-a[i]%k+j)%k]+1)

解释一下，指的是上一层（前i-1个数字）余数一样的，和上一层再加上a[i]（前i个数字）[余数]+1。

这里有个条件是要判断一下这个取模的余数是否已经存在了，不然就不能比较。

讲的不太清楚，看代码吧。

（这里用二维 vector存dp）

看！代码

#include <bits/stdc++.h>
using namespace std;
int a[100010];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    vector<vector<int> >dp(n+5);
    for(int i=0;i<=n;i++)
        dp[i].resize(k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=0;j<k;j++)
        {
            if(a[i]%k==j) dp[i][j]=1;
            dp[i][j]=max(dp[i-1][j],dp[i][j]);
            if(dp[i-1][(j-a[i]%k+k)%k]!=0)
                dp[i][j]=max(dp[i][j],dp[i-1][(j-a[i]%k+k)%k]+1);
        }
    printf("%d\n",dp[n][0]);
    return 0;
}