首页 > 代码库 > UVA-10003 Cutting Sticks (区间DP)
UVA-10003 Cutting Sticks (区间DP)
题目链接:https://vjudge.net/problem/UVA-10003
思路:
- 石子合并问题的逆过程,做法一模一样;
Code:
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a[60], dp[60][60], sum[60][60]; 4 5 int main() { 6 int l, n; 7 while(cin>>l>>n, l) { 8 memset(dp, 0, sizeof(dp)); 9 memset(sum, 0, sizeof(sum)); 10 int now, last = 0; 11 for (int i = 0; i < n; ++i) { 12 cin>>now; 13 a[i] = now - last; 14 last = now; 15 } 16 a[n] = l - last; 17 for (int i = 0; i <= n; ++i) 18 for (int j = i; j <= n; ++j) 19 sum[i][j] = sum[i][j-1] + a[j]; 20 for (int L = 2; L <= n + 1; ++L) 21 for (int i = 0; i + L - 1 <= n; ++i){ 22 int j = i + L - 1; 23 dp[i][j] = dp[i][i] + dp[i+1][j] + sum[i][j]; 24 for (int k = i; k < j; ++k) 25 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[i][j]); 26 } 27 cout<<"The minimum cutting is "<<dp[0][n]<<"."<<endl; 28 } 29 30 return 0; 31 }
UVA-10003 Cutting Sticks (区间DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。