首页 > 代码库 > 区间DP-----石子归并
区间DP-----石子归并
orz 上海的王队长。
1.最朴素的石子归并-codevs 1048
题目描述 Description
有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。
输入描述 Input Description
第一行一个整数n（n<=100）
第二行n个整数w1,w2...wn (wi <= 100)
输出描述 Output Description
一个整数表示最小合并代价
样例输入 Sample Input
4
4 1 1 4
样例输出 Sample Output
18
数据范围及提示 Data Size & Hint
n<=100
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define maxn 1100#define inf 0x7fint dp[maxn][maxn];int sum[maxn];int main() { int n; scanf("%d",&n); memset(dp,inf,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%d",&sum[i]); sum[i]+=sum[i-1]; dp[i][i]=0; } for(int i=n-1;i>=1;i--) for(int j=i+1;j<=n;j++) for(int k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]); printf("%d",dp[1][n]); return 0;}2.环上的石子归并-codevs 2102
题目描述 Description
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入描述 Input Description
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出描述 Output Description
输出共2行,第1行为最小得分,第2行为最大得分.
样例输入 Sample Input
4
4 4 5 9
样例输出 Sample Output
43
54
数据范围及提示 Data Size & Hint
n<=100
#include<cstdio>#include<cstring>#include<algorithm> using namespace std;#define maxn 1100#define inf (1<<30)int dp1[maxn][maxn]={0};int dp2[maxn][maxn];int sum[maxn];int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&sum[i]); sum[i+n]=sum[i]; } n<<=1; for(int i=1;i<=n;i++) sum[i]+=sum[i-1]; for(int i=n-1;i>=1;i--) for(int j=i+1;j<=n;j++) { int sumij=sum[j]-sum[i-1],dp=inf; for(int k=i;k<j;k++) { dp=min(dp,dp1[i][k]+dp1[k+1][j]+sumij); dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sumij); } dp1[i][j]=dp; } int ans1=inf,ans2=0; n>>=1; for(int i=1;i<=n;i++) { ans1=min(ans1,dp1[i][i+n-1]); ans2=max(ans2,dp2[i][i+n-1]); } printf("%d\n%d",ans1,ans2); return 0;}3.四边形不等式优化的石子归并-codevs 3002
题目描述 Description
有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。
输入描述 Input Description
第一行一个整数n（n<=3000）
第二行n个整数w1,w2...wn (wi <= 3000)
输出描述 Output Description
一个整数表示最小合并代价
样例输入 Sample Input
4
4 1 1 4
样例输出 Sample Output
18
数据范围及提示 Data Size & Hint
数据范围相比“石子归并” 扩大了
#include<cstdio>#include<cstring>#include<algorithm> using namespace std;#define maxn 5010#define inf (1<<30)int dp[maxn][maxn];int sum[maxn];int mid[maxn][maxn];int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&sum[i]); sum[i]+=sum[i-1]; dp[i][i]=0; mid[i][i]=i; } for(int r=1;r<n;r++) for(int i=1;i<n;i++) { int j=i+r; if(j>n) break; dp[i][j]=inf; for(int k=mid[i][j-1];k<=mid[i+1][j];k++) if(dp[i][j]>dp[i][k]+dp[k+1][j]) { dp[i][j]=dp[i][k]+dp[k+1][j]; mid[i][j]=k; } dp[i][j]+=sum[j]-sum[i-1]; } printf("%d",dp[1][n]); return 0;}
区间DP-----石子归并
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。