1044: [HAOI2008]木棍分割
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1393 Solved: 497
[Submit][Status]
Description
有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长度最大的一段长度最小. 并将结果mod 10007。。。
Input
输入文件第一行有2个数n,m. 接下来n行每行一个正整数Li,表示第i根木棍的长度.
Output
输出有2个数, 第一个数是总长度最大的一段的长度最小值, 第二个数是有多少种砍的方法使得满足条件.
Sample Input
3 2
1
1
10
1
1
10
Sample Output
10 2
两种砍的方法: (1)(1)(10)和(1 1)(10)
数据范围
n<=50000, 0<=m<=min(n-1,1000).
1<=Li<=1000.
前半部分为极水的二分，后半部分的DP优化很经典.用f[i][j]表示砍了i此到第j个末的方法种数，直接用一般的DP暴空间+时间，改为滚动数组后还是TLE。可以发现DP中后一层完全有前一层的一个连续区间决定的，且这些区间起点终点都是递增的。便可借此优化。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN 50010
#define MAXM 1010
#define VAL1 10007
#define VAL2 1100
int le[MAXN];
int n,m;
int f[][MAXN];
int ps[MAXN]; bool ok(int x)
{
int nowl=,tt=m;
int i;
for (i=;i<=n;i++)
{
if (le[i]>x)return false;
nowl+=le[i];
if (nowl>x)
{
nowl=le[i];
tt--;
if (tt==-)return false;
}
}
if (tt<=-)return false;
return true;
}
void deal(int &x,int y)
{
x+=y;x%=VAL1;
}
int q[MAXN*];
int main()
{
freopen("input.txt","r",stdin);
int i,j;
scanf("%d%d",&n,&m);
int sum=;
for (i=;i<=n;i++)scanf("%d",le+i),sum+=le[i];
for (i=;i<=n;i++)ps[i]=ps[i-]+le[i];
ps[]=le[];
int ans1,ans2=;
int l=,r=sum,mid;
while (l+<r)
{
mid=(l+r)>>;;
if (ok(mid))
{
r=mid;
}else
{
l=mid;
}
}
ans1=r;
int * a,*b;
int ope,clo,res;
f[][]=;
a=f[];b=f[];
for (i=;i<m;i++)
{
res=a[];
ope=,clo=;
q[]=;
for (j=;j<=n;j++)
{
while (ope<=clo&&ps[j]-ps[q[ope]]>ans1)
{
res-=a[ope++];
if(res<)res+=VAL1;
}
b[j]=res;
res+=a[++clo];
q[clo]=j;
res%=VAL1;
}
for (j=n-;j>=;j--)//这里不是n，Wa了好久
{
if (ps[n]-ps[j]>ans1)break;
ans2+=b[j];
ans2%=VAL1;
}
memset(a,,sizeof(int)*MAXN);
swap(a,b);
} /*
f[0][0]=1;
for (i=1;i<=n;i++)
{
for (j=i;j>0;j--)
{
if (ps[i]-ps[j-1]>ans1)break;
for (k=0;k<m;k++)
{
deal(f[i%VAL2][k+1],f[(j-1)%VAL2][k]);
}
}
}
for (i=n;i>=1;i--)
{
if (ps[n]-ps[i]>ans1)break;
ans2=(ans2+f[i%VAL2][m])%VAL1;
}*/
printf("%d %d\n",ans1,ans2); }