ABC281D数学动态规划与记忆和搜索

#include <stdio.h>
#include <string.h>
#define N 105
#define LL long long
int n, m, i, j, k, x, s, a[N];
LL ans, f[N][N][N];
LL dfs(int k, int c, int r){
    if(c > m) return -1e18;//恰好m个且余数为0才行
    if(k > n) return r==0&&c==m ? 0 : -1e18;
    else{
        if(~f[k][c][r]) return f[k][c][r];
        LL p = dfs(k+1, c, r), q;//填1和0选不选
        q = dfs(k+1, c+1, (r+a[k])%x) + a[k];
        return f[k][c][r] = p>q ? p : q;
    }
}//前k-1个数字，选了c个，余数是r
int main(){
    scanf("%d%d%d", &n, &m, &x);
    for(i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    memset(f, -1, sizeof(f));
    ans = dfs(1, 0, 0);
    if(ans < 0) ans = -1;
    printf("%lld\n", ans);
    return 0;
}