题解 P2511 【[HAOI2008]木棍分割】
y2823774827y
2019-02-16 09:22:22
一眼题系列，本题似乎没有暴力分~~整个题就是暴力~~
$(1)$二分解决
$(2)$ 1. 二分预处理$let[i]$ 为能与第$i$个组成块的最左边位置，不过本题没卡$O(n^2)$也可过
$~~~~~~$2.$dp[i][j]$为第$i$个为第$j$块结尾的方案数：
$~~~~~~~~dp[i][j]=\sum\limits_{k=let[i]}^idp[k-1][j-1]$显然空间时间都会爆
$~~~~~~~~$改成滚动数组，套个前缀和
取模和$long long$这里注意一下不开O2也能过~~本人太懒~~
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn=50009,p=10007;
LL n,m,sum,ans,num,now,lst;
LL a[maxn],let[maxn],dp[2][maxn],pre[2][maxn];
inline bool Check(LL x){
LL len(0),ret(1);
for(LL i=1;i<=n;++i){
if(a[i]>x) return false;
len+=a[i];
if(len>x) ++ret,len=a[i];
}
return ret<=m?true:false;
}
int main(){
scanf("%lld%lld",&n,&m); ++m;
for(LL i=1;i<=n;++i) scanf("%lld",a+i),sum+=a[i];
LL l(1),r(sum);
while(l<=r){
LL mid(l+r>>1);
if(Check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
for(LL i=1;i<=n;++i){
LL len(0);
for(LL j=i;j>=1;--j){
len+=a[j];
if(len>ans){
let[i]=j+1;
break;
}
}
if(!let[i]) let[i]=1;
}
now=0,lst=1;
for(LL i=0;i<=n;++i) pre[0][i]=1;
for(LL j=1;j<=m;++j){
now^=1,lst^=1;
memset(pre[now],0,sizeof(pre[now]));
memset(dp[now],0,sizeof(dp[now]));
for(LL i=1;i<=n;++i){
if(i<j)
dp[now][i]=0;
else if(let[i]-2>=0)
dp[now][i]=(pre[lst][i-1]-pre[lst][let[i]-2]+p)%p;
else
dp[now][i]=pre[lst][i-1];
pre[now][i]=(pre[now][i-1]+dp[now][i])%p;
}
num=(num+dp[now][n])%p;
}
printf("%lld %lld",ans,num);
return 0;
}
```