首页 > 代码库 > 洛谷1880 石子合并
洛谷1880 石子合并
P1880 石子合并
题目描述
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入输出格式
输入格式：
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式：
输出共2行,第1行为最小得分,第2行为最大得分.
输入输出样例
输入样例#1：
44 5 9 4
输出样例#1：
4354
上午做题的时候，一个小同学问我此题，说实话我并没有做过环形的石子合并，这也算是练了练手
np[i][j]代表从i开始长度为j的一段石子合并起来的最小成绩
xp[i][j] 代表从i开始长度为j的一段石子合并起来的最大成绩
关于环形怎么解决，请看图
对于n种石子的情况，就会有n种计算方法，在这n个方法中取个最大或最小即可。
（蓝色石子是复制品）
代码这次写的比较工整
#include<iostream>using namespace std;int n,st[210],sum[210][210];int xp[210][210],np[210][210],mn,mx;int main(){ cin>>n; for(int i=1;i<=n;i++) {cin>>st[i];st[i+n]=st[i];} for(int i=1;i<=n*2-1;i++)sum[1][i]=st[i]+sum[1][i-1]; for(int i=1;i<=n*2-1;i++) for(int j=i;j<=n*2-1;j++) sum[i][j]=sum[1][j]-sum[1][i-1]; for(int i=n*2;i>=1;i--){ for(int j=i+1;j<=min(i+n,n*2);j++){ np[i][j]=99999999; for(int k=i;k<j;k++){ xp[i][j]=max(xp[i][k]+xp[k+1][j]+sum[i][k]+sum[k+1][j],xp[i][j]); np[i][j]=min(np[i][k]+np[k+1][j]+sum[i][k]+sum[k+1][j],np[i][j]); } } } mn=99999999; for(int i=1;i<=n-1;i++){ mn=min(mn,np[i][i+n-1]); mx=max(mx,xp[i][i+n-1]); } cout<<mn<<endl<<mx;}
洛谷1880 石子合并
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。