Luogu P2511 [HAOI2008]木棍分割二分+DP

思路：二分+DP

提交：3次

错因：二分写萎了，$cnt$记录段数但没有初始化成$1$,$m$切的次数没有$+1$

思路：

先二分答案，不提；

然后有个很$naive$的$DP$:

设$f[i][j]$表示分成$i$段，到第$j$个木棍的方案数,$l$表示二分后的答案，

所以有$f[i][j]=sum_{j到k+1根木棍的总长度leq l}$ $f[i-1][k]$

$ans=sum_{i=1}^{m+1}f[i][n]$

但他太慢了$QwQ$

于是我们优化一下：

把$f[i-1][1]$到$f[i-1][k]$前缀和一下记做$s[i-1][k]$，这样可以$O(1)$查区间；

然后对于每个木棍$j$，预处理"$j$到$k+1$根木棍的总长度$leq l$"中的$k$，记为$pos[j]$

所以现在有$f[i][j]=s[i-1][j]-s[i-1][pos[j]-1]$

然后惊喜地发现第一维可以滚掉？！

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define ull unsigned long long
#define ll long long
#define R register ll
#define pause (for(R i=1;i<=10000000000;++i))
#define In freopen("NOIPAK++.in","r",stdin)
#define Out freopen("out.out","w",stdout)
namespace Fread {
static char B[1<<15],*S=B,*D=B;
#ifndef JACK
#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
#endif
inline int g() {
    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
    if(ch==EOF) return EOF; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
} inline bool isempty(const char& ch) {return (ch<=36||ch>=127);}
inline void gs(char* s) {
    register char ch; while(isempty(ch=getchar()));
    do *s++=ch; while(!isempty(ch=getchar()));
}
} using Fread::g; using Fread::gs;

namespace Luitaryi {
const int N=50010,M=10007;
int n,m,pos[N];
ll ans,mx,a[N],sum[N],f[N],s[N];
inline bool ck(int x) { R cnt=1,sum=0;
    for(R i=1;i<=n;++i) {
        if(sum+a[i]>x) sum=0,++cnt;
        sum+=a[i];
        if(cnt>m+1) return false;
    }    return cnt<=m+1;
}
inline void main() {
    n=g(),m=g();
    for(R i=1;i<=n;++i) a[i]=g(),mx=max(a[i],mx),sum[i]=sum[i-1]+a[i];
    R l=mx,r=sum[n]+1;
    while(l<r) {
        R md=l+r>>1; if(ck(md)) r=md;
        else l=md+1;
    } printf("%d ",l); R p=0;
    for(R i=1;i<=n;++i) {
        while(sum[i]-sum[p]>l&&p<i) ++p;
        pos[i]=p;
    }
    for(R i=1;i<=n;++i) f[i]=sum[i]<=l,s[i]=(s[i-1]+f[i]); ans=sum[n]<=l;
    for(R i=2;i<=m+1;++i) { 
        for(R j=1;j<=n;++j) { 
            f[j]=s[j-1];
            if(pos[j]-1>0) f[j]=((f[j]-s[pos[j]-1])%M+M)%M;
        }
        for(R j=1;j<=n;++j) s[j]=(s[j-1]+f[j])%M;
        ans=(ans+f[n])%M;
    } printf("%lld
",ans);
}
}
signed main() {
    Luitaryi::main();
    return 0;
}

2019.07.19

Luogu P2511 [HAOI2008]木棍分割 二分+DP

Luogu P2511 [HAOI2008]木棍分割二分+DP