CF 189A Cut Ribbon

#include<bits/stdc++.h>

using namespace std;

const int maxn = 4000 + 131;

int n, a, b, c;

int Dp[maxn];

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    cin >> n >> a >> b >> c;

    memset(Dp,0,sizeof(Dp));

    Dp[a] = Dp[b] = Dp[c] = 1;

    for(int i = 0; i <= n; ++i)

    {

        /// 前一种状态必须是被填过的

        if(i >= a && Dp[i-a]) Dp[i] = max(Dp[i], Dp[i-a]+1);

        if(i >= b && Dp[i-b]) Dp[i] = max(Dp[i], Dp[i-b]+1);

        if(i >= c && Dp[i-c]) Dp[i] = max(Dp[i], Dp[i-c]+1);

    }

    cout << Dp[n] << endl;

}

巴特西

CF 189A Cut Ribbon

最新文章

热门文章