aximum-Cup 2018 D Many Go Round(3)

結局こんな感じのDPを書いた。

INF = 10**9+7

def rec(pos, j):
    if pos == N:
        if j == L:
            return 0
        return INF
    # pos 番目を使わない
    ans = rec(pos+1, j)
    ans = min(ans, rec(pos+1, (j+a[pos])%M)+(j+a[pos])//M)
    return ans

ans = rec(0, 0)
print(ans)
print('Yes') if ans < X else print('No')

これをC++に移して、ACした。

#include <cstdio>
#include <algorithm>
using namespace std;

int N, M, L, X;
int a[10000];
int dp[10001][1001];

#define INF 10e6+7;

int main() {
    scanf("%d %d %d %d", &N, &M, &L, &X);
    for (int i = 0; i < N; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j < M; j++) {
            dp[i][j] = INF;
        }
    }
    dp[N][L] = 0;
    for (int i = N-1; i > -1; i--) {
        for (int j = 0; j < M; j++) {
            dp[i][j] = min(dp[i+1][j], dp[i+1][(j+a[i])%M]+(j+a[i])/M);
        }
    }
    if (dp[0][0] < X) {
        puts("Yes");
    } else {
        puts("No");
    }
    return 0;
}

ACできた。ヤッター。