[蓝桥杯][2018年第九届真题]倍数问题

朴素做法，(01)背包。时间复杂度：(O(4nm))。

状态表示：

(f(i,j,k))：从前(i)个数中选，总和模(K)的余数为(j)，且当前已选的数的个数为(k)个。

状态转移：

[f(i,j,k)=max(f(i-1,j-w[i],k-1)+w[i],f(i-1,j,k)) ]

边界：

(f(0,0,0)=0)，即初始一个数都没选的情况下，总和为(0)，模(k)的余数为(0)，其他状态均为(-inf)（表示不合法状态）。

const int N=1e5+10,M=1e3+10;
int f[2][M][5];
int w[N];
int n,m;

int get(int x)
{
    return (x%m+m)%m;
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++) cin>>w[i];
    
    memset(f,-0x3f,sizeof f);
    f[1][w[1]%m][1]=w[1];
    f[1][0][0]=0;
    for(int i=2;i<=n;i++)
        for(int j=0;j<m;j++)
            for(int k=0;k<=3;k++)
            {
                f[i&1][j][k]=f[i-1&1][j][k];
                if(k) f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][get(j-w[i])][k-1]+w[i]);
            }
    
    cout<<f[n&1][0][3]<<endl;
    //system("pause");
    return 0;
}