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<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int i,j,l,k,n,a[105],f[105][105],s[105];
int main()
{
    scanf("%d",&n);
    s[0] = 0;
    for(i = 1;i <= n;i++)
    {
        scanf("%d",&a[i]);
        s[i] = s[i - 1] + a[i];
    }
    for(l = 2;l <= n;l++)
    {
        for(i = 1;i <= n + l - 1;i++)
        {
            j = i + l - 1;
            for(k = i;k <= j - 1;k++)
            {
                if(f[i][j] != 0)
                f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
                else
                f[i][j] = f[i][k] + f[k + 1][j] + s[j] - s[i - 1];
            }
        }
    }
    printf("%d",f[1][n]);
    return 0;
}

第二种是围成一个圈那样，和这道题就是这个类型
O（N^3)有两种算法
第一种就是

 

这种啊博主也没怎么看懂，等着2020年6月9号看吧吼吼
下面这种博主还是会滴

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int i,j,m,n,l,k,da = 0,an = 0,a[205],f[205][205],s[205],p[205][205];
int main()
{
    scanf("%d",&n);
    s[0] = 0;
    for(i = 1;i <= n;i++)
    {
        scanf("%d",&a[i]);
        a[i + n] = a[i];
    }
    for(i = 1;i <= 2 * n;i++)
    {
        s[i] = s[i - 1] + a[i];
    }
    for(l = 2;l <= n;l++)
    {
        for(i = 1;i <= n * 2 - l;i++)
        {
            j = i + l - 1;
            for(k = i;k <= j - 1;k++)
            {
                if(f[i][j] != 0)
                f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
                else
                f[i][j] = f[i][k] + f[k + 1][j] + s[j] - s[i - 1];
                p[i][j] = max(p[i][j],p[i][k] + p[k + 1][j] + s[j] - s[i - 1]);
            }     
        }
    }
    for(i = 1;i <= n;i++)
    {
        if(da != 0)
        da = min(da,f[i][i + n - 1]);
        else
        da = f[i][i + n - 1];
        an = max(an,p[i][i + n - 1]);
    }
    printf("%d
%d",da,an);
    return 0;
}