[HAOI2008]木棍分割题解

本文主要是介绍[HAOI2008]木棍分割题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

分析

第一问是最简单的二分答案，就不说了。第二问则要用到dp中的隔板法，对于本题就是找到一个节点i能到达的最左端lef[i]（连续子段和<=第一问中的答案），f[i][j]代表前i个数分成j块的方案数,则f[i][j]=Σ f[k][j-1] (k>=lef[i]&&k＜i) ，而因为空间问题，是不可以开1000x50000数组的，所以一个数组f记录当前j的所有i的答案，而s记录j-1的所有i的答案的前缀和。每次求完本轮之后再更新s。
时间：2500ms。
上代码

#include<bits/stdc++.h>
using namespace std;
int now=0,n,m,al[50010],l=1,r=50000000,ans1,mod=10007,ans2,f[50005],s[50005],lef[50005];
bool work(int x){int k=0,t=1;for(int i=1;i<=n;i++)if(al[i]>x)return false;else if(k+al[i]>x){t++,k=al[i];if(t>m) return false;}else k+=al[i];return true;
}
int main(){memset(f,0,sizeof(f));scanf("%d%d",&n,&m);m++;for(int i=1;i<=n;i++)scanf("%d",&al[i]);while(l<=r){int mid=(l+r)/2;if(work(mid))r=mid-1,ans1=mid;elsel=mid+1;}for(int i=1;i<=n;i++){al[i]+=al[i-1];while(al[i]-al[now]>ans1)now++;lef[i]=now;}fill(s,s+n+1,1);for(int i=1;i<=m;i++){for(int j=1;j<=n;j++)f[j]=(s[j-1]-s[lef[j]-1])%mod;s[0]=0;for(int j=1;j<=n;j++)s[j]=f[j]+s[j-1];ans2=(ans2+f[n])%mod;}printf("%d %d\n",ans1,ans2);return 0;
}

这篇关于[HAOI2008]木棍分割题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---