[动态规划]切钢管

[动态规划]切钢管

今天咱们来聊聊动态规划的另外一个趣味题：
给定一段长度为n的钢条和一个价格表，求切割钢条方案，使得销售收益最大。

——数据源：《算法导论》

不妨定义dp[x]为长度x的钢条所能收获最大利益，这么一想，原问题具有最有子结构的性质，用动态规划大法解之！显然问题的答案是dp[length]

#include <iostream>
#include <algorithm>
using namespace std;
const int v[] = {0,1,5,8,9,10,17,17,20,24,30};
int dp[34];int main() {int L;cin >> L;for (int i = 1; i <= L; ++i) {int q = -1;for (int j = 1; j <= i; ++j) {q = max(q,v[j]+dp[i-j]);}dp[i] = q;}cout << dp[L] << endl;return 0;
}