首页 > 代码库 > luogu P1880 石子合并
luogu P1880 石子合并
题目描述
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入输出格式
输入格式：
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式：
输出共2行,第1行为最小得分,第2行为最大得分.
输入输出样例
输入样例#1：
44 5 9 4
输出样例#1：
4354
区间动态规划
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;inline int min(int x,int y){ if(x<y)return x;return y; }inline int max(int x,int y){ if(y>x)return y;return x;}int a[203];int dp_max[203][203];int dp_min[203][203];int main(){ int n; scanf("%d",&n); memset(dp_max,0,sizeof(dp_max)); for(int i=1;i<=2*n;i++) for(int j=i+1;j<=2*n;j++) dp_min[i][j]=0x7fffffff; for(int i=1;i<=n;i++)scanf("%d",a+i),a[i+n]=a[i]; for(int i=2;i<=n*2;i++)a[i]+=a[i-1]; for(int i=n*2-1;i>=1;i--) { for(int j=i+1;j<=n*2;j++) { for(int k=i;k<j;k++) { dp_min[i][j]=min(dp_min[i][j],dp_min[i][k]+dp_min[k+1][j]+a[j]-a[i-1]); dp_max[i][j]=max(dp_max[i][j],dp_max[i][k]+dp_max[k+1][j]+a[j]-a[i-1]); } } } int minn=0x7fffffff; int maxx=-1; for(int i=1;i<=n;++i) { minn=min(dp_min[i][i+n-1],minn); maxx=max(dp_max[i][i+n-1],maxx); } printf("%d\n%d",minn,maxx); return 0;}
luogu P1880 石子合并
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。