#include<iostream>

#include<vector>

using namespace std;

class Solution {

public:

    int Bottom_To_Up_Cut_Rod(vector<int> p, int n) {

        vector<int> r(n);

        r[0] = 0;

        int q = -65533;

        for(int i = 1; i <= n; i++) {

            for(int j = 1; j <= i; j++) {

                q = q > (p[j] + r[i - j]) ? q : (p[j] + r[i - j]);

            }

            r[i] = q;

        }

        return r[n];

    }

};

int main() {

    int nums[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

    int len = (int)sizeof(nums)/sizeof(int);

    vector<int> p(len);

    Solution so;

    for(int i = 0; i < len; i++) {

        p[i] = nums[i];

    }

    cout << "请输入钢材的长度:";

    cin >> len;

    cout << "最大收益为:" << so.Bottom_To_Up_Cut_Rod(p, len) << endl;

    return 0;

}