K序列

题目描述

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

输入描述:

第一行为两个整数 n, K, 以空格分隔，第二行为 n 个整数，表示 a[1] ∼ a[n]，1 ≤ n ≤ 105 , 1 ≤ a[i] ≤ 109 , 1 ≤ nK ≤ 107

输出描述:

输出一个整数表示最长子序列的长度 m

输入

7 5
10 3 4 2 2 9 8

输出

6

分析

很简单的一题，不过暴力求解会超时，注意第18行不能写成for (j=0;j<i;j++)，否则超时。

AC代码

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int main()
{
    int i,j,n,k,count=0,sum=0;
    cin>>n>>k;
    int temp,dp[n+1];
    memset(dp,0,sizeof(dp));
    for (i=1;i<=n;i++)
    {
        cin>>temp;
        dp[i]=(temp+dp[i-1])%k;
    }
    for (i=0;i<=n;i++)
    {
        for (j=n;j>=i+sum;j--)
        {
            if (abs(dp[i]-dp[j])%k==0)
            sum=abs(i-j)>sum?abs(i-j):sum;
        }
    }
    cout<<sum;
}