首页 > 代码库 > NOIP模拟赛 czy的后宫6
NOIP模拟赛 czy的后宫6
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了很久）
最后一个点还会超时，明天来优化一下。。。（继续背模板）
1 #include<iostream> 2 using namespace std; 3 4 const int mod=32123; 5 6 int n,m,ans1,ans2; 7 int a[20001]; 8 int tot[1001]; 9 int f[20001][1001];10 11 bool check(int x)12 {13 int t=0,sum=0;14 for(int i=1;i<=n;i++)15 {16 sum+=a[i];17 if(sum>x) t++,sum=a[i];18 if(t>m||a[i]>x) return false;19 }20 return true;21 }22 23 void dp()24 {25 int l=0,sum=a[1];26 f[0][0]=0;27 for(int i=2;i<=n;i++)28 {29 sum+=a[i];30 while(sum-a[l]>ans1)31 {32 sum-=a[l];33 l++;34 }35 for(int j=1;j<=m;j++)36 for(int k=l;k<i;k++)37 {38 f[i][j]+=f[k][j-1];39 f[i][j]%=mod;40 }41 }42 for(int i=0;i<=m;i++)43 ans2=(ans2+f[n][i])%mod;44 }45 46 int main()47 {48 cin>>n>>m;49 int left=1,right=0,sum=0;50 for(int i=1;i<=n;i++)51 {52 cin>>a[i];53 right+=a[i];54 }55 while(left<right)56 {57 int mid=(left+right)>>1;58 if(check(mid))59 right=mid;60 else left=mid+1;61 }62 ans1=right;63 for(int i=0;i<=n;i++)64 {65 sum+=a[i];66 if(sum>ans1) break;67 f[i][0]=1;68 }69 dp();70 cout<<ans1<<endl<<ans2<<endl;71 return 0;72 }
NOIP模拟赛 czy的后宫6
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。