Codeforces 189A - A. Cut Ribbon
長さ n のリボンある。そのリボンを出来るだけたくさんカットしたい。カットされたリボンの長さは、a, b, cのいずれかでなければならない。最大でいくつのリボンにカットできるか、という問題。
制約:
1 <= n, a, b, c <= 4000
DPの問題なのでC++で解きました。
#include <algorithm> #include <cassert> #include <cstdio> #include <iostream> using namespace std; const int N = 4001; int calc(int n, int a, int b, int c) { int dp[N] = {}; int xs[] = { a, b, c }; for (int i = 0; i < 3; i++) { dp[xs[i]] = max(dp[xs[i]], 1); for (int j = xs[i]+1; j <= n; j++) { if (dp[j-xs[i]] > 0) dp[j] = max(dp[j], 1 + dp[j-xs[i]]); } } assert(dp[n] != 0); return dp[n]; } int main() { int n, a, b, c; scanf("%d %d %d %d", &n, &a, &b, &c); printf("%d\n", calc(n, a, b, c)); }
こういうDPの問題ってHaskellだとどういう風にかけばいいのかな。