acwing1234. 倍数问题

题目

题解

朴素dp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10, M=1010;

int n, m;
int a[N];
int f[N][5][M];

signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);

    memset(f, -0x3f, sizeof f);
    for(int i=0;i<=n;i++) f[i][0][0]=0;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=3;j++)
            for(int k=0;k<m;k++)
                f[i][j][k]=max(f[i-1][j][k], f[i-1][j-1][((k-a[i])%m+m)%m]+a[i]);

    int ans=-1;
    for(int i=1;i<=n;i++) ans=max(ans, f[i][3][0]);
    cout<<ans<<endl;
}

作者：白之月
链接：https://www.acwing.com/solution/content/43862/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

优化

只有考虑余数

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=1010;
int n,m;
vector<int> a[N];
int f[4][N];
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        a[x%m].push_back(x);
    }
    memset(f,-0x3f,sizeof f);
    f[0][0]=0;
    for(int i=0;i<m;i++){
        sort(a[i].begin(),a[i].end());
        reverse(a[i].begin(),a[i].end());
        for(int u=0;u<a[i].size()&&u<=3;u++){
            int x=a[i][u];
            for(int j=3;j>=1;j--){
                for(int k=0;k<m;k++){
                    f[j][k]=max(f[j][k],f[j-1][(k-x%m+m)%m]+x);
                }
            }
        }
    }
    cout<<f[3][0]<<endl;
    return 0;
}