CF 189 A Cut Ribbon
687 ワード
簡単dp...切断後のブロックはa b cの1つでなければならないので、状態遷移時に前の状態が到達可能であることに注意してください(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;
}