BZOJ1044: [HAOI2008]木棍分割【二分+DP】

1044: [HAOI2008]木棍分割

【题目描述】

传送门

【题解】

我们可以二分出最小值,然后去做DP,然后压一下位加前缀和优化就可以了。

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=50005;
const int MAXM=1005;
const int MOD=10007;
int n,m,Ans1,Ans2,D[MAXN];
int Sum[MAXN],Low,f[MAXN][2],A[MAXN][2];
inline void MO(int &x){if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
inline bool check(int x){
    memset(D,63,sizeof(D));D[0]=0;
    for(int i=1,k=0;i<=n;i++){for(;Sum[i]-Sum[k]>x&&k<i;k++);D[i]=min(D[i],D[k]+1);}
    return D[n]<=m;
}
inline int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;
    return f?ret:-ret;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1044.in","r",stdin);
    freopen("1044.out","w",stdout);
    #endif
    n=read(),m=read()+1;
    for(int i=1;i<=n;i++) Sum[i]=read(),Low=max(Low,Sum[i]),Sum[i]+=Sum[i-1];
    for(register int L=Low,R=1e7,mid=(R+L)>>1;L<=R;mid=(R+L)>>1)
    if(check(mid)) Ans1=mid,R=mid-1;else L=mid+1;
    f[0][0]=1;for(int i=0;i<=n;i++) A[i][0]=1;//赋初值
    for(register int j=1;j<=m;MO(Ans2+=f[n][(j++)&1]),A[0][j&1]=0)//DP
    for(register int i=1,k=0,p=j&1;i<=n;i++){
        for(;Sum[i]-Sum[k]>Ans1&&k<i;k++); 
        MO(f[i][p]=(A[i-1][p^1]-(k?A[k-1][p^1]:0))),MO(A[i][p]=f[i][p]+A[i-1][p]);
    }
    if(Ans1==0) printf("0 0\n");else printf("%d %d\n",Ans1,Ans2);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部