「czy系列赛」czy的后宫6

2014年7月19日3,4790

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

题解

改编自木棍

第一问二分即可，第二问写出60分的dp然后用个队列优化转移即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 32123
using namespace std;
inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,ans1,ans2;
int a[20005];
int f[20005][1005];
int tot[1005];
bool jud(int x)
{
	int tmp=0,sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=a[i];
		if(sum>x){tmp++;sum=a[i];}
		if(tmp>m)return 0;
		if(a[i]>x)return 0;
	}
	return 1;
}
void solve1()
{
	int l=1,r=6000000;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(jud(mid)){ans1=mid;r=mid-1;}
		else l=mid+1;
	}
}
void dp()
{
	int sum=0;
	f[0][0]=1;tot[0]=1;
	int l=0;
	for(int i=1;i<=n;i++)
	{
		sum+=a[i];
		while(sum-a[l]>ans1)
	    {
	    	sum-=a[l];
	    	for(int j=0;j<=m+1;j++)
	    	{
	    	    tot[j]-=f[l][j];
	    	    if(tot[j]<mod)tot[j]+=mod;
	    	}
	    	l++;
	    }
	    for(int j=m+1;j>=1;j--)
	    {
	    	f[i][j]+=tot[j-1];
	    	tot[j]+=f[i][j];
	    	tot[j]%=mod;
	    	f[i][j]%=mod;
	    }
	}
	for(int i=0;i<=m+1;i++)
	    ans2=(ans2+f[n][i])%mod;
}
int main()
{
	//freopen("visit.in","r",stdin);
	//freopen("visit.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	solve1();
	printf("%d\n",ans1);
	dp();
	printf("%d",ans2);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define mod 32123

using namespace std;

inline ll read()

{

ll x=0,f=1;char ch=getchar();

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

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

return x*f;

}

int n,m,ans1,ans2;

int a[20005];

int f[20005][1005];

int tot[1005];

bool jud(int x)

{

int tmp=0,sum=0;

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

{

sum+=a[i];

if(sum>x){tmp++;sum=a[i];}

if(tmp>m)return 0;

if(a[i]>x)return 0;

}

return 1;

}

void solve1()

{

int l=1,r=6000000;

while(l<=r)

{

int mid=(l+r)>>1;

if(jud(mid)){ans1=mid;r=mid-1;}

else l=mid+1;

}

void dp()

{

int sum=0;

f[0][0]=1;tot[0]=1;

int l=0;

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

{

sum+=a[i];

while(sum-a[l]>ans1)

{

sum-=a[l];

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

{

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

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

}

l++;

}

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

{

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

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

tot[j]%=mod;

f[i][j]%=mod;

}

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

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

}

int main()

{

//freopen("visit.in","r",stdin);

//freopen("visit.out","w",stdout);

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

for(int i=1;i<=n;i++)a[i]=read();

solve1();

printf("%d\n",ans1);

dp();

printf("%d",ans2);

return 0;

}

« 「czy系列赛」czy的后宫4 「fj夏令营」解释器 »

hzwer.com _ Home | http://hzwer.com

「czy系列赛」czy的后宫6

分类目录

热门文章

Myfriends

近期评论