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

样例输出

样例解释

最小的肾虚值为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段时的方案数

 #include<iostream>

 using namespace std;

 const int mod=;

 int n,m,ans1,ans2;

 int a[];

 int tot[];

 int f[][];

 int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-f;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 bool check(int x)

 {

     int t=,sum=;

     for(int i=;i<=n;i++)

     {

         sum+=a[i];

         if(sum>x) t++,sum=a[i];

         if(t>m||a[i]>x) return false;

     }

     return true;

 }

 void dp()

 {

     int l=,sum=;

     tot[]=;f[][]=;

     for(int i=;i<=n;i++)

     {

         sum+=a[i];

         while(sum-a[l]>ans1)

         {

             sum-=a[l];

             for(int j=;j<=m+;j++)

             {

                 tot[j]-=f[l][j];

                 if(tot[j]<mod) tot[j]+=mod;

             }

             l++;

         }

         for(int j=m+;j>=;j--)

         {

             f[i][j]+=tot[j-];

             tot[j]+=f[i][j];

             tot[j]%=mod;

             f[i][j]%=mod;

         }

     }

     for(int i=;i<=m+;i++)

         ans2=(ans2+f[n][i])%mod;

 }

 int main()

 {

     n=read();m=read();

     int left=,right=;

     for(int i=;i<=n;i++)

     {

         a[i]=read();

         right+=a[i];

     }

     while(left<right)

     {

         int mid=(left+right)>>;

         if(check(mid))

             right=mid;

         else left=mid+;

     }

     ans1=right;

     dp();

     cout<<ans1<<endl<<ans2<<endl;

     return ;

 }

巴特西

NOIP模拟赛 czy的后宫6

最新文章

热门文章