POJ 2750 Potted Flower(线段树+dp）

虽然是看的别的人思路，但是做出来还是挺高兴的。

首先求环上最大字段和，而且不能是含有全部元素。本来我的想法是n个元素变为2*n个元素那样做的，这样并不好弄。实际可以求出最小值，总和-最小，就可以求出，断开的情况了。

然后线段树要单点更新，这种标记，以前遇到过，不过一直没有写过，注意总和好更新，整个这一段的结果也很好更新，最难想的就是左边和右边标记的结果，具体看pushup代码。

 #include <cstring>

 #include <cstdio>

 #include <string>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 using namespace std;

 #define maxn 100100

 struct node

 {

     int sum,lmax,lmin,rmin,rmax;

     int smax,smin;

 }p[*maxn];

 void pushup(int rt)

 {

     p[rt].sum = p[rt<<].sum + p[rt<<|].sum;

     p[rt].smax = max(max(p[rt<<].smax,p[rt<<|].smax),p[rt<<].rmax+p[rt<<|].lmax);

     p[rt].lmax = max(p[rt<<].lmax,p[rt<<].sum+p[rt<<|].lmax);

     p[rt].rmax = max(p[rt<<|].rmax,p[rt<<|].sum+p[rt<<].rmax);

     p[rt].smin = min(min(p[rt<<].smin,p[rt<<|].smin),p[rt<<].rmin + p[rt<<|].lmin);

     p[rt].lmin = min(p[rt<<].lmin,p[rt<<].sum+p[rt<<|].lmin);

     p[rt].rmin = min(p[rt<<|].rmin,p[rt<<|].sum+p[rt<<].rmin);

 }

 void build(int l,int r,int rt)

 {

     int m;

     if(l == r)

     {

         scanf("%d",&p[rt].sum);

         p[rt].lmax = p[rt].sum;

         p[rt].rmax = p[rt].sum;

         p[rt].smax = p[rt].sum;

         p[rt].lmin = p[rt].sum;

         p[rt].rmin = p[rt].sum;

         p[rt].smin = p[rt].sum;

         return ;

     }

     m = (l+r)>>;

     build(l,m,rt<<);

     build(m+,r,rt<<|);

     pushup(rt);

 }

 void update(int x,int sc,int l,int r,int rt)

 {

     int m;

     if(l == x&&r == x)

     {

         p[rt].sum = sc;

         p[rt].lmax = p[rt].sum;

         p[rt].rmax = p[rt].sum;

         p[rt].smax = p[rt].sum;

         p[rt].lmin = p[rt].sum;

         p[rt].rmin = p[rt].sum;

         p[rt].smin = p[rt].sum;

         return ;

     }

     m = (l+r)>>;

     if(x <= m)

     update(x,sc,l,m,rt<<);

     if(x > m)

     update(x,sc,m+,r,rt<<|);

     pushup(rt);

 }

 int main()

 {

     int n,m,i,a,b;

     while(scanf("%d",&n)!=EOF)

     {

         build(,n,);

         scanf("%d",&m);

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

         {

             scanf("%d%d",&a,&b);

             update(a,b,,n,);

             if(p[].sum == p[].smax)//如果总和和最大值相同，断开一个最小值。

             {

                 printf("%d\n",p[].sum - p[].smin);

             }

             else

             {

                 printf("%d\n",max(p[].smax,p[].sum-p[].smin));

             }

         }

     }

     return ;

 }

巴特西

POJ 2750 Potted Flower(线段树+dp）

最新文章

热门文章