首页 > 代码库 > 51nod1021(区间dp)
51nod1021(区间dp)
题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1021
题意:中文题诶~
思路:区间dp
我们用num[i]存储前i个元素的和,用dp[i][j]存储合并从第i个到第j个元素的代价,那么有动态转移方程式为:
dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+num[j]-num[i-1]);
还有一个问题:如果我们直接枚举i, j的话有可能我们在计算dp[i][j]时dp[k+1][j]还没计算出来,这样我们自然不能得到正确答案咯.
其实我们只要换个思路就能解决这个问题啦,我们枚举len, 和i,len表示当前合并的区间长度为len,那么j=i+len-1.
这样就不会有上面的问题啦,因为区间i,k和区间k+1,j的长度一定小于区间i, j的长度,即在计算dp[i][j]之前我们已经计算出dp[i][k]和dp[k+1][j]啦.
代码:
1 #include <bits/stdc++.h>
2 #define MAXN 110
3 using namespace std;
4
5 int a[MAXN], num[MAXN], dp[MAXN][MAXN]; //***dp[i][j]存储第i堆到第j堆的合并代价
6 const int inf=0x3f3f3f3f;
7
8 int main(void){
9 int n, ans=0;
10 cin >> n;
11 for(int i=1; i<=n; i++){
12 cin >> a[i];
13 num[i]=num[i-1]+a[i];
14 }
15 for(int len=2; len<=n; len++){
16 for(int i=1; i<n; i++){
17 int j=i+len-1; //***这里要注意j可能会大于n
18 if(j<=n){
19 dp[i][j]=inf;
20 for(int k=i; k<j; k++){
21 dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+num[j]-num[i-1]);
22 }
23 }
24 }
25 }
26 cout << dp[1][n] << endl;
27 }
51nod1021(区间dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。