M_sea

洛谷2511 [HAOI2008]木棍分割
LuoguBZOJ分析毒瘤二合一第一问比较简单,直接二分答案即可,check应该都会。第二问,设$f[i][j]$...
扫描右侧二维码阅读全文
21
2019/01

洛谷2511 [HAOI2008]木棍分割

Luogu

BZOJ

分析

毒瘤二合一

第一问比较简单,直接二分答案即可,check应该都会。

第二问,设$f[i][j]$表示前$j$根木棍分成$i$组的方案数。

然后显然有$f[i][j]=\sum\limits_{l=k}^{j-1}f[i-1][l]$,这里的$k$是满足$k$到$j$的和最小的$k$。

显然每个$j$对应的$k$是单调的,所以可以$O(n)$处理出每个$k$。

再用前缀和维护一下$\texttt{DP}$数组,然后$\texttt{DP}$数组和这个前缀和数组都可以上滚动数组。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;
const int MOD=10007;

int n,m,l[N];
int ans;

inline int check(int mid) {
    for (re int i=1,now=0,s=0;i<=n;++i) {
        if (now+l[i]>mid) ++s,now=l[i];
        else now+=l[i];
        if (s>m) return 0;
    }
    return 1;
}

inline void solve1() {
    int L=0,R=0;
    for (re int i=1;i<=n;++i) L=max(L,l[i]),R+=l[i];
    while (L<R) {
        int mid=(L+R)>>1;
        if (check(mid)) R=mid;
        else L=mid+1;
    }
    ans=L; printf("%d ",L);
}

int sum[N],f[N],S[N],o[N];

inline void solve2() {
    for (re int i=1;i<=n;++i) sum[i]=sum[i-1]+l[i];
    int res=(sum[n]<=ans);
    for (re int i=1,j=0;i<=n;++i)
        for (;j<i;++j)
            if (sum[i]-sum[j]<=ans) { o[i]=j-1; break; }
    for (re int i=1;i<=n;++i) {
        if (sum[i]<=ans) f[i]=1;
        S[i]=(S[i-1]+f[i])%MOD;
    }
    for (re int i=2;i<=m+1;++i) {
        for (re int j=1;j<=n;++j) {
            f[j]=S[j-1];
            if (o[j]>=0) f[j]=((f[j]-S[o[j]])%MOD+MOD)%MOD;
        }
        for (re int j=1;j<=n;++j) S[j]=(S[j-1]+f[j])%MOD;
        res=(res+f[n])%MOD;
    }
    printf("%d\n",res);
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) l[i]=read();
    solve1(); solve2();
    return 0;
}
最后修改:2019 年 01 月 21 日 03 : 03 PM

发表评论