CF 189 A Cut Ribbon

簡單dp。。。由於切割後沒塊必須是a b c中一個，所以注意狀態轉移時前一個狀態必須是可到達的(f[i] != 0)。。。

#include<iostream>
#include<cstring>
using namespace std;

int n, a, b, c;
int f[4444];

int main()
{
    while(cin>>n>>a>>b>>c)
    {
        memset(f, 0, sizeof(f));
        f[a] = f[b] = f[c] = 1;
        for(int i=1; i<=n; i++)
        {
            if(i > a && f[i-a])   f[i] = max(f[i], f[i-a] + 1);
            if(i > b && f[i-b])   f[i] = max(f[i], f[i-b] + 1);
            if(i > c && f[i-c])   f[i] = max(f[i], f[i-c] + 1);
        }
        cout<<f[n]<<endl;
    }
    return 0;
}