洛谷 P1121 环状最大两段子段和

https://www.luogu.org/problemnew/show/P1121

不会做啊。。。

看题解讲的：

答案的两段可能有两种情况：一是同时包含第1和第n个，2是不同时包含第1和第n个

对于第二种可以先求出f[i],g[i]分别表示1..i和i..n的最大子段和，然后枚举断点解决

对于第一种可以转化成找到“序列上最小两段字段和“去掉，这可以用第二种的方法解决；不过注意这个”序列上最小两段字段和“长度必须<=n-2（因为要剩下至少2个元素），需要一些特判

另外，话说此题居然还能用线段树维护...

（然而数据弱，仍然不知道以下代码是不是对的）

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 #define int ll

 struct pii

 {

     int fi,se;

     pii():fi(),se(){}

     pii(int a,int b):fi(a),se(b){}

 };

 pii max1(const pii &a,const pii &b)

 {

     return (a.fi<b.fi||(a.fi==b.fi&&a.se>b.se))?b:a;

 }

 pii min1(const pii &a,const pii &b)

 {

     return (a.fi<b.fi||(a.fi==b.fi&&a.se<b.se))?a:b;

 }

 int a[];

 pii f1[],g1[],f2[],g2[];

 int n,a1,a2,sum;

 int calc(int p)

 {

     if(p==)

     {

         return g2[].se==n- ? g2[].fi-max(a[],a[n]) : g2[].fi;

     }

     else if(p==n)

     {

         return f2[n-].se==n- ? f2[n-].fi-max(a[],a[n-])

             : f2[n-].fi;

     }

     else

     {

         return f2[p-].se+g2[p+].se==n-

             ? f2[p-].fi+g2[p+].fi - max(max(a[],a[p-]),

                 max(a[p+],a[n]))

             : f2[p-].fi+g2[p+].fi;

     }

 }

 signed main()

 {

     int i;pii t;

     scanf("%lld",&n);

     if(n<=)    exit(-);

     for(i=;i<=n;++i)

     {

         scanf("%lld",&a[i]);

         sum+=a[i];

     }

     f1[]=pii(a[],);

     t=pii(a[],);

     if(t.fi<=)    t=pii(,);

     for(i=;i<=n;++i)

     {

         t.fi+=a[i];++t.se;

         f1[i]=max1(f1[i-],t);

         if(t.fi<=)    t=pii(,);

     }

     g1[n]=pii(a[n],);

     t=pii(a[n],);

     if(t.fi<=)    t=pii(,);

     for(i=n-;i>=;--i)

     {

         t.fi+=a[i];++t.se;

         g1[i]=max1(g1[i+],t);

         if(t.fi<=)    t=pii(,);

     }

     f2[]=pii(a[],);

     t=pii(a[],);

     if(t.fi>=)    t=pii(,);

     for(i=;i<=n;++i)

     {

         t.fi+=a[i];++t.se;

         f2[i]=min1(f2[i-],t);

         if(t.fi>=)    t=pii(,);

     }

     g2[n]=pii(a[n],);

     t=pii(a[n],);

     if(t.fi>=)    t=pii(,);

     for(i=n-;i>=;--i)

     {

         t.fi+=a[i];++t.se;

         g2[i]=min1(g2[i+],t);

         if(t.fi>=)    t=pii(,);

     }

     a1=f1[].fi+g1[].fi;

     for(i=;i<=n-;++i)

         a1=max(a1,f1[i].fi+g1[i+].fi);

     a2=calc();

     for(i=;i<=n;++i)

         a2=min(a2,calc(i));

     printf("%lld",max(a1,sum-a2));

     return ;

 }