石子合并

链接：https://ac.nowcoder.com/acm/problem/50493
来源：牛客网

将n堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。
请编写一个程序，读入堆数n及每堆的石子数，并进行如下计算：
选择一种合并石子的方案，使得做n-1次合并得分总和最大。
选择一种合并石子的方案，使得做n-1次合并得分总和最小。
输入描述:
输入第一行一个整数n，表示有n堆石子。
第二行n个整数，表示每堆石子的数量。
输出描述:
第一行为合并得分总和最小值，
第二行为合并得分总和最大值。
示例1
4
4 5 9 4
输出
43
54
备注:
对于100 %100%的数据，有1 \leq n \leq 2001≤n≤200。

解：
先把石子从⚪型简化到一条链，用区间DP的思路来解的话，先要找出状态转移方程。
用dp[i][j]表示在i到j区间内最大（最小）石子合并总分，枚举i，j，再枚举中间的分割点k，i<k<j。
找到最优分点k，依次递推，找到最优解。
解决了链状，⚪型如何放在一条链上。用一点小技巧，把数据读入2次，4 5 9 4 4 5 9 4，就可以化⚪为链，操作方便。

#include <bits/stdc++.h>
using namespace std;
int dp[205][205];
int lst[410];
int summ(int i,int j)
{
    int temp=0;
    for (int k=i;k<=j;k++)
    temp+=lst[k];
    return temp;
}
int main()
{
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) 
    cin>>lst[i];
    for (int i=n+1;i<=2*n;i++)
    lst[i]=lst[i-n];//相当于读两遍
    int maxi=0,mini=0x3f3f3f3f;//设置初始值
    for (int i=2*n;i>=1;i--)//从后往前推，类似01背包
    {
        for (int j=i+1;j<=i+n-1&& j<=2*n;j++)
        for (int k=i;k<=j-1;k++)
        {
            dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+summ(i,j));//枚举k，寻找最优解
            if (j-i+1==n)
            maxi=max(dp[i][j],maxi);            
        }
    }    
    memset(dp,0,sizeof(dp));
    for (int i=2*n;i>=1;i--)
    {
        for (int j=i+1;j<=i+n-1 && j<=2*n;j++)
        for (int k=i;k<=j-1;k++)
        {
            if (dp[i][j]>0)
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+summ(i,j));
            else
                dp[i][j]=dp[i][k]+dp[k+1][j]+summ(i,j);
            if (j-i+1==n)
            mini=min(dp[i][j],mini);
        }
    }            
    cout<<mini<<endl;
    cout<<maxi<<endl;
    system ("pause");
    return 0;
}