Description
有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长度最大的一段长度最小. 并将结果mod 10007。n<=50000,0<=m<=min(n-1,10
00),1<=Li<=1000.
第一问二分答案水过。
第二问恶(zuo)心(si)了我大概有一下午。
朴素dp方案:
dp[i][j]表示前i个木棍分成j段的方案数。转移方程：其中[lim,j]为最长的以j结尾的合法区间。空间大概190MB,单调队列预处理lim的话，时间大概O()。
考虑前缀和优化：dp[i][j]表示i个区间[1,1~i]分成j段的方案数。那么则有：dp[i][j]=dp[i-1][j]+dp[i-1][j-1]-dp[lim-2][j-1]。时间O(nm)
空间的话发现第二维是单调递增的，那么交换两维。循环数组进行dp,那么ans=可以循环的时候统计答案。
不过下面题解描述暂时不交换，比较好看。
当然，可以再用一次前缀和思想：dp[i][j]表示i个区间[1,1~i]至多分成j段的方案数。转移：dp[i][j]=dp[i-1][j]+dp[i-1][j-1]-dp[lim-2][j-1]。证明其不重复：dp[i-1][j]的方案数结尾端点<j，dp[i-1][j-1]-dp[lim-2][j-1]统计的方案数为加上第j个木棍的分发。高兴的发现真的不重不漏。
那么ans=dp[n][m]-dp[n-1][m]咦？？和上面的比较一下，为啥dp转移方程相同，而ans的统计却不同呢？？？
啊！！！初值。dp[0][j]在上一个dp方案中仅当j=0的时候为1.其他时候都为0.
那？？？我还优化个头啊？？？初值直接O(n)。算了吧，想到了就写吧。
然后练(xue)习了一下卡常。嗯。循环展开还有mod替换(据说在O2环境下效果甚佳？？？)
__attribute__((always_inline))，这个还没弄懂。。。编译不过我也不知道什么情况。。。
还有数组循环顺序+读入优化。
成功从2700ms+优化到2100ms+。(话说一开始写的好像就很快)
代码不忍直视。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define rint register int
int n,m,c,a[50010],ans;
void read(int &x)
{
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
}
int Max(int x,int y){return x>y?x:y;}
bool check(int x)
{
rint i,now=0,cnt=0;
for(i=1;i!=c;++i)
{
now+=a[i];
if(now>x) now=a[i],cnt++;
}
return m>=cnt;
}
int bin[50010],dp[2][50010];
const int mod=10007;
int inc(int x,int v){x+=v;return x>=mod?x-mod:x;}
int dec(int x,int v){x-=v;return x<0?x+mod:x;}
int main()
{
read(n); read(m);c=n+1;
rint i,j,l=-1,r=50000000,mid;
for(i=1;i!=c;++i) read(a[i]),l=Max(a[i],l);
while(l<r)
{
mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
ans=r; printf("%d ",ans);
rint now=0;r=n,l=n+1;
while(r)
{
while(now<ans&&l>1) now+=a[--l];
if(now>ans) now-=a[l++];
bin[r]=l; now-=a[r--];
}
rint fl=1,cc=m+2;
for(i=0;i!=cc;++i,fl^=1)
{
dp[fl][0]=1;
for(j=1;j<=n;j+=16)
{
dp[fl][j]=(bin[j]==1)?inc(dp[fl][j-1],dp[fl^1][j-1]):dec(inc(dp[fl][j-1],dp[fl^1][j-1]),dp[fl^1][bin[j]-2]);
dp[fl][j+1]=(bin[j+1]==1)?inc(dp[fl][j],dp[fl^1][j]):dec(inc(dp[fl][j],dp[fl^1][j]),dp[fl^1][bin[j+1]-2]);
dp[fl][j+2]=(bin[j+2]==1)?inc(dp[fl][j+1],dp[fl^1][j+1]):dec(inc(dp[fl][j+1],dp[fl^1][j+1]),dp[fl^1][bin[j+2]-2]);
dp[fl][j+3]=(bin[j+3]==1)?inc(dp[fl][j+2],dp[fl^1][j+2]):dec(inc(dp[fl][j+2],dp[fl^1][j+2]),dp[fl^1][bin[j+3]-2]);
dp[fl][j+4]=(bin[j+4]==1)?inc(dp[fl][j+3],dp[fl^1][j+3]):dec(inc(dp[fl][j+3],dp[fl^1][j+3]),dp[fl^1][bin[j+4]-2]);
dp[fl][j+5]=(bin[j+5]==1)?inc(dp[fl][j+4],dp[fl^1][j+4]):dec(inc(dp[fl][j+4],dp[fl^1][j+4]),dp[fl^1][bin[j+5]-2]);
dp[fl][j+6]=(bin[j+6]==1)?inc(dp[fl][j+5],dp[fl^1][j+5]):dec(inc(dp[fl][j+5],dp[fl^1][j+5]),dp[fl^1][bin[j+6]-2]);
dp[fl][j+7]=(bin[j+7]==1)?inc(dp[fl][j+6],dp[fl^1][j+6]):dec(inc(dp[fl][j+6],dp[fl^1][j+6]),dp[fl^1][bin[j+7]-2]);
dp[fl][j+8]=(bin[j+8]==1)?inc(dp[fl][j+7],dp[fl^1][j+7]):dec(inc(dp[fl][j+7],dp[fl^1][j+7]),dp[fl^1][bin[j+8]-2]);
dp[fl][j+9]=(bin[j+9]==1)?inc(dp[fl][j+8],dp[fl^1][j+8]):dec(inc(dp[fl][j+8],dp[fl^1][j+8]),dp[fl^1][bin[j+9]-2]);
dp[fl][j+10]=(bin[j+10]==1)?inc(dp[fl][j+9],dp[fl^1][j+9]):dec(inc(dp[fl][j+9],dp[fl^1][j+9]),dp[fl^1][bin[j+10]-2]);
dp[fl][j+11]=(bin[j+11]==1)?inc(dp[fl][j+10],dp[fl^1][j+10]):dec(inc(dp[fl][j+10],dp[fl^1][j+10]),dp[fl^1][bin[j+11]-2]);
dp[fl][j+12]=(bin[j+12]==1)?inc(dp[fl][j+11],dp[fl^1][j+11]):dec(inc(dp[fl][j+11],dp[fl^1][j+11]),dp[fl^1][bin[j+12]-2]);
dp[fl][j+13]=(bin[j+13]==1)?inc(dp[fl][j+12],dp[fl^1][j+12]):dec(inc(dp[fl][j+12],dp[fl^1][j+12]),dp[fl^1][bin[j+13]-2]);
dp[fl][j+14]=(bin[j+14]==1)?inc(dp[fl][j+13],dp[fl^1][j+13]):dec(inc(dp[fl][j+13],dp[fl^1][j+13]),dp[fl^1][bin[j+14]-2]);
dp[fl][j+15]=(bin[j+15]==1)?inc(dp[fl][j+14],dp[fl^1][j+14]):dec(inc(dp[fl][j+14],dp[fl^1][j+14]),dp[fl^1][bin[j+15]-2]);
}
for(j=n-n%16+1;j!=c;++j)
dp[fl][j]=(bin[j]==1)?inc(dp[fl][j-1],dp[fl^1][j-1]):dec(inc(dp[fl][j-1],dp[fl^1][j-1]),dp[fl^1][bin[j]-2]);
}
printf("%d",dec(dp[fl^1][n],dp[fl^1][n-1]));
return 0;
}