[SPOJ685 SEQPAR]数学归纳法证明、平衡树、动态规划、标记上传

【题库地址】https://www.spoj.pl/

进去找685就好，直接发地址的好像没有登录是看不了的。

【题目大意】

给定一个序列Ai，让你把他分成K组，使得每一组的和不超过M，问M最小能是多少？

1<=N<=15000

-30000<=Ai<=30000

【算法分析】

可以用数学归纳法证明：假设已经确定了M，然后设能构成合法分组的最小组数为min，能构成合法分组的最大组数为max，那么对于x∈[min,max]，则x必然存在一个合法分组方式。（即解的连续性）

然后剩下的就是动态规划。

Fmin[i]为A1..Ai这个序列，最少能划分为多少组，使之成为一个合法序列。

然后Fmin[i]=min{Fmin[j]+1} (s[i]-s[j]<=M)

同理Fmax也一样求。

然后转移那个地方用一个平衡树维护一下就好，平衡树以s[i]为key值，然后上面加一个类似线段树的标记，然后随时更新就好。

【其它】1A。

这题一点思路都没有，只能找GXX大神要解题报告了

Orz GXX 大神。。。

【CODE】

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
const int N=15111;
const int INF=1000000000;
int n,part;
int Fmax[N],Fmin[N],a[N],s[N],nowi;
struct SBTtype{
       struct point{int l,r,zz,Min,Max,s;}tr[N];
       int tot,root;
      
       inline void update(int &p){
              if (!p) return;
              tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
              tr[p].Min=Fmin[tr[p].zz];
              if (tr[p].l && tr[tr[p].l].Min<tr[p].min) tr[p].min=”tr[tr[p].l].Min;<br”>              if (tr[p].r && tr[tr[p].r].Min<tr[p].min) tr[p].min=”tr[tr[p].r].Min;<br”>              tr[p].Max=Fmax[tr[p].zz];
              if (tr[p].l && tr[tr[p].l].Max>tr[p].Max) tr[p].Max=tr[tr[p].l].Max;
              if (tr[p].r && tr[tr[p].r].Max>tr[p].Max) tr[p].Max=tr[tr[p].r].Max;
       }
      
       void left(int &p){
            int k=tr[p].r;
            tr[p].r=tr[k].l;
            tr[k].l=p;
            update(p);
            update(k);
            p=k;
       }
      
       void right(int &p){
            int k=tr[p].l;
            tr[p].l=tr[k].r;
            tr[k].r=p;
            update(p);
            update(k);
            p=k;
       }
      
       void repair(int &p){
            if (!p) return;
            bool flag=false;
            if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
              right(p);
              flag=true;
            }
            if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
              left(tr[p].l);
              right(p);
              flag=true;
            }
            if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
              left(p);
              flag=true;
            }
            if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
              right(tr[p].r);
              left(p);
              flag=true;
            }
            if (flag){
              repair(tr[p].l);
              repair(tr[p].r);
              repair(p);
            }
       }
      
       void ins(int &p,int i){
            if (!p){
              p=++tot;
              tr[p].l=0; tr[p].r=0; tr[p].zz=i;
              update(p);
            }
            else{
              tr[p].s++;
              if (s[i]<s[tr[p].zz]) ins(tr[p].l,i);<br=””>                               else ins(tr[p].r,i);
              update(p);
              repair(p);
            }
       }
      
       int Findmin(int &p,int key){
           if (!p) return INF;
           if (s[tr[p].zz]<key) return=”” findmin(tr[p].r,key);<br=””>           int re=Findmin(tr[p].l,key);
           re=min(re,Fmin[tr[p].zz]);
           if (tr[p].r) re=min(re,tr[tr[p].r].Min);
           return re;
       }
      
       int Findmax(int &p,int key){
           if (!p) return -INF;
           if (s[tr[p].zz]<key) return=”” findmax(tr[p].r,key);<br=””>           int re=Findmax(tr[p].l,key);
           re=max(re,Fmax[tr[p].zz]);
           if (tr[p].r) re=max(re,tr[tr[p].r].Max);
           return re;
       }
}sbt;</key)></key)></s[tr[p].zz])></tr[p].min)></tr[p].min)></iostream>
</cstring>
</cstdlib>
</cstdio>

void init(){
     scanf(“%d%d”,&n,&part);
     for (int i=1;i<=n;i++) scanf(“%d”,&a[i]);
     for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
}

bool can(int M){
     sbt.root=0; sbt.tot=0;
     sbt.ins(sbt.root,0);
     for (nowi=1;nowi<=n;nowi++){
         Fmin[nowi]=sbt.Findmin(sbt.root,s[nowi]-M)+1;
         Fmax[nowi]=sbt.Findmax(sbt.root,s[nowi]-M)+1;
         sbt.ins(sbt.root,nowi);
     }
     if (Fmin[n]<=part && part<=Fmax[n]) return true;
     return false;
}

void work(){
     int l=-INF,r=INF,mid;
     while (l<r){
           mid=(l+r)>>1;
           if (can(mid)) r=mid;
                    else l=mid+1;
     }
     printf(“%dn”,l);
}</r){

int main(){
//    freopen(“input.txt”,”r”,stdin);
//    freopen(“output.txt”,”w”,stdout);
    int Tc;
    cin >> Tc;
    for (int i=0;i<tc;i++){
        init();
        work();
    }
    return 0;
}</tc;i++){