Luogu P1880 石子合并 题解报告

题目传送门

【题目大意】

在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分。

【思路解析】

首先是断环为链，这题数据不大，没什么问题。

说一下转移方程吧$$f[l][r]=min(f[l][r],f[l][k]+f[k+1][r])+sum[r]-sum[l-1](lle k<r)$$初始值：详见代码

目标：$min(f[i][i+n-1])(iin[1,n]),max(g[i][i+n-1])(iin[1,n])$.

还有就是要注意一下循环嵌套的顺序，哪一个循环在里面，哪一个循环在外面。

【代码实现】

#include<bits/stdc++.h>
#define rg register
#define go(i,a,b) for(rg int i=a;i<=b;i++)
#define back(i,a,b) for(rg int i=a;i>=b;i--)
#define mod 2147483648
#define ll long long
using namespace std;
const int N=102<<1;
int n,a[N],sum[N];
ll f[N][N],g[N][N];
int main(){
    scanf("%d",&n);
    memset(f,0x3f,sizeof(f));memset(g,0,sizeof(g));
    go(i,1,n) scanf("%d",&a[i]),a[i+n]=a[i];
    go(i,1,n*2) f[i][i]=0,g[i][i]=0,sum[i]=sum[i-1]+a[i];
    go(len,2,n) go(l,1,2*n-len+1){
        int r=l+len-1;
        go(k,l,r-1){
            f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
            g[l][r]=max(g[l][r],g[l][k]+g[k+1][r]);
        }
        f[l][r]+=sum[r]-sum[l-1];
        g[l][r]+=sum[r]-sum[l-1];
    }
    ll ans1=123456798,ans2=0;
    go(i,1,n) ans1=min(ans1,f[i][i+n-1]),ans2=max(ans2,g[i][i+n-1]);
    printf("%lld
%lld
",ans1,ans2);
    return 0;
}