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できた。ヤッター。