bzoj 1044 贪心二分+DP

原题传送门http://www.lydsy.com/JudgeOnline/problem.php?id=1044

首先对于第一问，我们可以轻易的用二分答案来搞定，对于每一个二分到的mid值

我们从len[i]开始累加，每到累加值>mid的时候，就累加一个需要砍的次数，然后

比较次数和m的大小关系，然后二分就行了，这里有个小贪心，对于一个len[i]，我们

尽量的不让他消耗一次砍得次数，直到非砍不可了才砍。

那么问题就转化成了我们有N个木条的长度，用最多M刀将他们分为不超过ans长度的方案数

我们用w[j,i]代表砍j刀，前i个木条的方案数，那么可以轻易的得到转移方程

w[j,i]:=sigma(w[j-1,k]) sum[i]-sum[k-1]<=ans

其中sum是长度的前缀和

分析下，这个时间复杂度是n*n*m的，明显过不去，那么想下优化

我们可以知道，sum是不变的，换句话说，就是每个转移到I的k是不变的，且是连续区间

那么我们对于每个i，存下pre[i]，代表最早pre[i]能更新I，那么我们w[j,i]也存成前缀和，

对于每个w[j,i]就可以o(1)的转移了

而且这道题会卡空间，需要用滚动数组

自己的超时了，照着大神的改了改。。。

/**************************************************************

    Problem:

    User: BLADEVIL

    Language: Pascal

    Result: Accepted

    Time: ms

    Memory: kb

****************************************************************/

var

    w                           :array[..,-..] of longint;

    pre, a, s                   :array[-..] of longint;

    last                        :array[-..] of longint;

    p, ans2, tot                :longint;

    max, tmp                    :longint;

    i, j, h, k                  :longint;

    l, r, mid, ans              :longint;

    n, m                        :longint;

function check(x:longint):boolean;

var i                           :longint;

begin

    if max>x then exit(false);

    tmp:=;

    tot:=;

    for i:= to n do

    begin

        if tmp+a[i]<=x then tmp:=tmp+a[i]

        else begin

            tmp:=a[i];

            inc(tot);

            if tot>m then exit(false);

        end;

    end;

    exit(true);

end;

begin

    readln(n,m);

    if n= then

    begin

        writeln(,' ',);

        exit;

    end;

    for i:= to n do

    begin

        readln(a[i]);

        s[i]:=s[i-]+a[i];

        if max<a[i] then max:=a[i];

    end;

    l:=;

    r:=s[n];

    while l<r do

    begin

        if l=r- then

        begin

            if check(l) then ans:=l

                else ans:=r;

            break;

        end;

        mid:=(l+r) shr ;

        if check(mid) then r:=mid else l:=mid;

    end;

    tmp:=;

    tot:=;

    for i:= to n do

    begin

        if tmp+a[i]>ans then

        begin

            tmp:=a[i];

            inc(tot);

            last[tot]:=i-;

        end else tmp:=tmp+a[i];

    end;

    for i:=tot+ to m+ do last[i]:=n;

    h:=;

    for i:= to n do

    begin

        while s[i]-s[h]>ans do inc(h);

        pre[i]:=h;

    end; 

    for i:= to last[] do w[,i]:=w[,i-]+;

    for i:=last[]+ to last[] do w[,i]:=w[,i-];

    l:=;

    for i:= to m+ do

    begin

        k:=l;

        l:=k xor ;

        w[l,i]:=;

        p:=;

        for j:=i+ to last[i] do

        begin

            p:=w[k,j-]-w[k,pre[j]-];

            w[l,j]:=(w[l,j-]+p) mod ;

        end;

        if last[i]=n then ans2:=(ans2+p) mod

        else begin

            for j:=last[i]+ to last[i+] do w[l,j]:=w[l,j-];

        end;

    end;

    writeln(ans,' ',(ans2 mod +) mod );

end.

巴特西

bzoj 1044 贪心二分+DP

最新文章

热门文章