rod cutting.cpp

/*
    Author: Jerry Yang C.H. (tico88612)
    Date: 2020/5/13
*/
#include <bits/stdc++.h>
using namespace std;
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
/********** Good Luck :) **********/
int main()
{
    IOS();
    int c[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int p[10] = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
    int n;
    cin >> n;
    int dp[10000] = {0};
    for(int i = 0; i < 10; i++) {
        for (int j = c[i]; j <= n; j++) {
            dp[j] = max(dp[j], dp[j - c[i]] + p[i]);
        }
    }
    cout << dp[n] << '\n';
    return 0;
}