Codeforces 189A - A. Cut Ribbon

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だとどういう風にかけばいいのかな。