洛谷P1880 石子合并【区间型动态规划】
发布时间：2021年12月06日 20:12:12
发布人：jqh?
**题目描述**
在一个圆形操场的四周摆放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
```cpp
#include <iostream>
#include <cstdio>
#include <string.h>
#include <memory.h>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
int main()
{
int t,num[101],dpMin[100][100],dpMax[100][100]={{0}},n;//dp数组下标分别表示区间起始点和长度
cin>>n;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
dpMin[i][j]=0x7fffffff;
num[0]=0;
for(int i=0; i<n; ++i)
{
cin>>t;
num[i+1]=num[i]+t;
dpMin[i][0]=0;
}
int score;
for(int len=1; len<n; ++len)
for(int i=0; i<n; ++i)
{
if(i+len>=n)
score=num[n]-num[i]+num[(i+len)%n+1];
else
score=num[i+len+1]-num[i];
for(int k=0; k<len; ++k)
{
dpMin[i][len]=min(dpMin[i][len],dpMin[i][k]+dpMin[(i+k+1)%n][len-k-1]+score);
dpMax[i][len]=max(dpMax[i][len],dpMax[i][k]+dpMax[(i+k+1)%n][len-k-1]+score);
}
}
int ansMin=0x7fffffff,ansMax=0;
for(int i=0;i<n;++i)
{
ansMin=min(ansMin,dpMin[i][n-1]);
ansMax=max(ansMax,dpMax[i][n-1]);
}
cout<<ansMin<<endl<<ansMax;
return 0;
}
```
热门评论：