luogu P2511 [HAOI2008]木棍分割

第一问是一道经典的二分,二分答案\(ans\),然后从前往后扫,判断要分成几段救星了

第二问设\(f_{i,j}\)表示前\(i\)个数分成\(j\)段,每段之和不超过第一问答案的方案,转移就是从\(f_{k,j-1}(k<i,(a_{k+1}+...+a_i)\leq ans)\)转移过来,这些\(k\)是连续的一段,并且这一段随着dp过程整体右移,所以搞个变量记录一下合法转移之和,再动态维护救星了

#include<bits/stdc++.h>

#define LL long long

#define il inline

#define re register

#define db double

#define eps (1e-5)

using namespace std;

const int mod=10007;

il LL rd()

{

    LL x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int n,m,a[50010],f[2][50010];

il bool check(int mid)

{

  for(int i=1,k=1,su=0;i<=n;i++)

    {

      su+=a[i];

      if(su>mid) su=a[i],++k;

      if(k>m) return false;

    }

  return true;

}

int main()

{

  n=rd(),m=rd()+1;

  int l=0,r=0;

  for(int i=1;i<=n;i++) a[i]=rd(),l=max(l,a[i]),r+=a[i];

  int ans=r;

  while(l<=r)

    {

      int mid=(l+r)>>1;

      if(check(mid)) ans=mid,r=mid-1;

      else l=mid+1;

    }

  printf("%d ",ans);

  int nw=1,la=0;

  for(int i=1,su=0;i<=n;i++)

    {

      su+=a[i];

      if(su>ans) break;

      f[la][i]=1;

    }

  int a2=f[la][n];

  for(int j=2;j<=m;j++)

    {

      memset(f[nw],0,sizeof(f[nw]));

      for(int i=1,p=1,su=0,tm=0;i<=n;i++)

        {

          su+=a[i],tm+=f[la][i-1];

          while(su>ans) su-=a[p],tm-=f[la][p-1],++p;

          f[nw][i]=(tm=(tm%mod+mod)%mod);

        }

      a2=(a2+f[nw][n])%mod;

      nw^=1,la^=1;

    }

  printf("%d\n",a2);

  return 0;

}

巴特西

luogu P2511 [HAOI2008]木棍分割

最新文章

热门文章