P1880 [NOI1995]石子合并

洛咕

今天比赛考原题，我竟然B0了。

洛咕的这道题是可以用\(n^3\)来做的，数据范围只有100，但是我还是WA了。

因为是环形，所以断环为链，在后面复制一段过去，也就是\(a[i+n]=a[i]\)。

那么\(n^3\)的做法是:

1、枚举长度，这点很重要。

\[for(int~len=2;len<=n;++len)\]

2、枚举\(l\)，\(l\in [1,2n-len+1]\)，那么\(r=l+len-1\)。

3、枚举\(k\)，\(k\in [l,r)\)，那么可以列出方程:

\[f[l][r]=min\{f[l][k]+f[k][r]+sum[r]-sum[l-1]\}\]

其中\(f[l][l]=0,sum[i]\)为前缀和。

至于求最大值，反过来即可。

#include<bits/stdc++.h>
#define ll long long
#define N 205
using namespace std;
ll n,a[N],f[N][N],sum[N],g[N][N];
int main(){
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i],a[i+n]=a[i];
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=2*n;++i)f[i][i]=0,sum[i]=sum[i-1]+a[i];
    for(int len=2;len<=n;++len){
        for(int i=1;i<=2*n&&i+len-1<=2*n;++i){
            int j=i+len-1;
            for(int k=i;k<j;++k){
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
                g[i][j]=max(g[i][j],g[i][k]+g[k+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    ll ans1=1e15,ans2=0;
    for(int i=1;i<=n;++i){
        ans1=min(ans1,f[i][i+n-1]);
        ans2=max(ans2,g[i][i+n-1]);
    }
    cout<<ans1<<"\n"<<ans2<<endl;
    return 0;
}

GarsiaWachs算法

无证明的算法介绍

可以用链表维护，效果极其地好，可以做到\(O(nlogn)\)(太妙了)

分为两步。

1、从前往后扫到第一个\(k\)，使得\(a[k-1]\ge a[k+1]\)，那么把\(a[k-1]\)和\(a[k]\)合并。

2、再从\(k\)开始向前扫，扫到第一个比\(a[k-1]+a[k]\)大的点，把\(a[k-1]+a[k]\)挂到这个点的后面。

链表的头和尾的值为\(INF\)，这样才不会出现死循环。

不过对于环形的石子合并来说，好像只能朴素地拆环，于是复杂度达到了\(O(n^2logn)\)，但还是比\(O(n^3)\)好多了。

这个地方我换了一个求最大值的办法，区间\([l,r]\)最大值只与\([l+1,r]\)和\([l,r-1]\)有关，所以我们可以得到

\[f[i][j]=max\{f[i+1][j],f[i][j-1]\}+s[j]-s[i-1]\]

其中\(s[i]\)为前缀和。

接下来是代码时间

#include<bits/stdc++.h>
#define int long long
#define N 205
#define INF (1<<30)
using namespace std;
struct node{
    int next,to,ds;
}a[N<<1];
int n,w[N],cnt,ans1=1e9,ans2,s[N],f[N][N];
void erase(int x){
    a[a[x].to].next=a[x].next;
    a[a[x].next].to=a[x].to;
}
void insert(int x){
    a[x].to=a[a[x].next].to;
    a[a[x].to].next=x;
    a[a[x].next].to=x;
}
void solve1(){
    int now=1,sum=0;
    for(int i=1;i<n;++i){
        while(1){
            if(a[a[now].next].ds<=a[a[now].to].ds)break;
            now=a[now].to;
        }
        int yyb=a[now].ds+a[a[now].next].ds;
        erase(a[now].next);erase(now);//cout<<now<<" "<<a[now].next<<" "<<yyb<<endl;
        sum+=yyb;
        int t=now;
        //cout<<1<<endl;
        while(1){
            if(a[a[t].next].ds>yyb){
                a[now].next=a[t].next;
                a[now].ds=yyb;
                insert(now);
                break;
            }
            t=a[t].next;
        }
        now=t;
    }
    ans1=min(ans1,sum);
}
main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&w[i]),w[i+n]=w[i];
    for(int i=1;i<=n;++i){
        a[n+2].to=1;a[n+1].next=n;
        a[n+2].ds=INF;a[n+1].ds=INF;
        for(int j=1;j<=n;++j){
            a[j].next=j-1;a[j].to=j+1;
            a[j].ds=w[i+j-1];
        }
        a[1].next=n+2;a[n].to=n+1;
        solve1();
    }
    for(int i=1;i<=n+n;++i)s[i]=s[i-1]+w[i];
    for(int i=n+n-1;i;--i){
        for(int j=i+1;j<=n+n;++j){
            f[i][j]=max(f[i][j-1],f[i+1][j])+s[j]-s[i-1];
        }
    }
    for(int i=1;i<=n;++i){
        ans2=max(ans2,f[i][i+n-1]);
    }
    printf("%d\n%d\n",ans1,ans2);
    return 0;
}

P1880 [NOI1995]石子合并

原文：https://www.cnblogs.com/fenghuazhengmao/p/11586851.html