第一问，明显的二分答案+验证。
第二问，dp[i][j]表示前j段切i刀的满足第一问的方案数，然后dp[i][j]=sigma(dp[i-1][k]) （k满足第一问限制）
显然在循环j的时候是可以算出来这个值的，所以总复杂度是n*m的。
其实我一开始写的是dp[i][j]表示前i个切j刀的方案数，显然这样写不能优化。。。
然后写出方程，发现调换i、j就可以了~
View Code
1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <algorithm> 6 7 #define N 55555 8 #define MOD 10007 9 10 using namespace std; 11 12 int n,m,a[N],l,r,mid; 13 int sum[N],ans,ans1; 14 int dp[2][N],q[N]; 15 16 inline void read() 17 { 18 scanf("%d%d",&n,&m); 19 for(int i=1;i<=n;i++) 20 { 21 scanf("%d",&a[i]); 22 l=max(l,a[i]); 23 sum[i]=sum[i-1]+a[i]; 24 } 25 } 26 27 inline bool check() 28 { 29 int gs=m,p=1,sm; 30 while(gs!=0&&p<=n) 31 { 32 sm=0; 33 while(p<=n&&sm+a[p]<=mid) sm+=a[p++]; 34 gs--; 35 } 36 if(p<=n&&sum[n]-sum[p-1]>mid) return false; 37 return true; 38 } 39 40 inline void step1() 41 { 42 r=sum[n]; 43 while(l<=r) 44 { 45 mid=(l+r)>>1; 46 if(check()) ans=mid,r=mid-1; 47 else l=mid+1; 48 } 49 printf("%d ",ans); 50 } 51 52 inline void step2() 53 { 54 dp[0][0]=1; 55 for(int i=1;i<=m;i++) 56 { 57 int h=1,t=0,res; 58 q[++t]=0; res=dp[(i-1)&1][0]; 59 for(int j=1;j<=n;j++) 60 { 61 while(h<=t&&sum[j]-sum[q[h]]>ans) 62 { 63 res-=dp[(i-1)&1][q[h]]; h++; 64 res%=MOD; 65 if(res<0) res+=MOD; 66 } 67 dp[i&1][j]=res; 68 q[++t]=j; res+=dp[(i-1)&1][j]; 69 res%=MOD; 70 } 71 for(int j=n-1;j>=1;j--) 72 { 73 if(sum[n]-sum[j]>ans) break; 74 ans1+=dp[i&1][j]; 75 ans1%=MOD; 76 } 77 memset(dp[(i-1)&1],0,sizeof dp[(i-1)&1]); 78 } 79 printf("%d\n",ans1); 80 } 81 82 inline void go() 83 { 84 step1(); 85 step2(); 86 } 87 88 int main() 89 { 90 read(),go(); 91 return 0; 92 }