P1880 [NOI1995]石子合并
题目描述
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入输出格式
输入格式：
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表*示每堆石子的个数.
输出格式：
输出共2行,第1行为最小得分,第2行为最大得分.
输入输出样例
输入样例1：
4 4 5 9 4
输出样例1：
43 54
代码
#include<cstdio>
#include<queue>
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
int n,maxx,minn=2147483646,a[201],f[201][201],s[201][201];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[n+i]=a[i];
}
for(int i=1;i<=2*n;i++){
a[i]=a[i]+a[i-1];
}
for(int r=2;r<=n;r++){
for(int i=1;i<=2*n-r+1;i++){
int j=i+r-1;
s[i][j]=s[i+1][j]+a[j]-a[i-1];
f[i][j]=f[i+1][j]+a[j]-a[i-1];
for(int k=i;k<j;k++){
s[i][j]=min(s[i][j],s[i][k]+s[k+1][j]+a[j]-a[i-1]);
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+a[j]-a[i-1]);
}
}
}
maxx=f[1][n],minn=s[1][n];
for(int i=2;i<=n;i++){
if(s[i][i+n-1]<minn){minn=s[i][i+n-1];}
if(f[i][i+n-1]>maxx){maxx=f[i][i+n-1];}
}
printf("%d\n%d\n",minn,maxx);
return 0;
}
开两个数组记录——最小&最大。
优质内容筛选与推荐>>1、android-轻松监听来电和去电
2、ME21N 创建采购订单
3、JAVA OOP 基础知识提纲
4、ECG - Pace Detection 起搏信号检测(1)
5、JQuery在线帮助文档