czy的后宫6
题目描述
众所周知的是丧尸czy有很多妹子（虽然很多但是质量不容乐观QAQ），今天czy把n个妹子排成一行来检阅。但是czy的妹子的质量实在……所以czy看不下去了。检阅了第i个妹子会增加czy a[i]的肾虚值，他打算在检阅过程中最多休息m次（一开始检阅算0次休息，就是说czy最多可以检阅m+1次），每次休息过后czy又会龙精虎猛的继续检阅。问怎样分配才能使得czy在检阅过程中的最大肾虚值最小。
当然这么简单的问题czy早就会做啦……他原来还想算算满足肾虚值最小的条件下有几种方案，但是他太虚了，所以这个问题也交给你啦。你只要输出方案数mod 32123的值即可。
输入格式
第一行输入两个正整数n、m，表示czy的妹子数、最多的休息次数
接下来2到n+1行每行输入一个数a[i]，意义见上
输出格式
第一行输出一个数s，表示最小的肾虚值
第二行输出一个数t，表示方案数
样例输入
4 2
3
4
5
2
样例输出
7
3
样例解释
最小的肾虚值为7
分法有3种：34|5|2，34|52，3|4|52
‘|’表示休息
数据范围
有30%的数据，1<=n<=20
另30%的数据，1<=n<=200
另30%的数据，1<=n<=5000，1<=m<=min(n-1,1000)，1<=a[i]<=1000
另10%的数据，1<=n<=20000，1<=m<=1000，a[i]只有1、2
保证80%数据随机生成，在计算过程中不会爆int
状态转移方程写出来就很简单了（虽然debug了很久）
f[i][j]表示前i个数，分割j-1段时的方案数
1 #include<iostream> 2 using namespace std; 3 4 const int mod=32123; 5 6 int n,m,ans1,ans2; 7 int a[20005]; 8 int tot[1005]; 9 int f[20005][1005]; 10 11 int read() 12 { 13 int x=0,f=1;char ch=getchar(); 14 while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();} 15 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 16 return x*f; 17 } 18 19 bool check(int x) 20 { 21 int t=0,sum=0; 22 for(int i=1;i<=n;i++) 23 { 24 sum+=a[i]; 25 if(sum>x) t++,sum=a[i]; 26 if(t>m||a[i]>x) return false; 27 } 28 return true; 29 } 30 31 void dp() 32 { 33 int l=0,sum=0; 34 tot[0]=1;f[0][0]=1; 35 for(int i=1;i<=n;i++) 36 { 37 sum+=a[i]; 38 while(sum-a[l]>ans1) 39 { 40 sum-=a[l]; 41 for(int j=0;j<=m+1;j++) 42 { 43 tot[j]-=f[l][j]; 44 if(tot[j]<mod) tot[j]+=mod; 45 } 46 l++; 47 } 48 for(int j=m+1;j>=1;j--) 49 { 50 f[i][j]+=tot[j-1]; 51 tot[j]+=f[i][j]; 52 tot[j]%=mod; 53 f[i][j]%=mod; 54 } 55 } 56 for(int i=0;i<=m+1;i++) 57 ans2=(ans2+f[n][i])%mod; 58 } 59 60 int main() 61 { 62 n=read();m=read(); 63 int left=1,right=0; 64 for(int i=1;i<=n;i++) 65 { 66 a[i]=read(); 67 right+=a[i]; 68 } 69 while(left<right) 70 { 71 int mid=(left+right)>>1; 72 if(check(mid)) 73 right=mid; 74 else left=mid+1; 75 } 76 ans1=right; 77 dp(); 78 cout<<ans1<<endl<<ans2<<endl; 79 return 0; 80 }