Math Show

时间: 1ms        内存:128M

描述:

Polycarp参加数学展。他被赋予n个任务,每个任务由k个子任务组成,编号为1到k。他花了tj分钟来解决任何任务的第j个子任务。因此,解决子任务所需的时间仅取决于其索引,而不取决于任务本身。Polycarp可以按任何顺序解决子任务。  
解决了任意问题的子任务,他都能获得了一分。因此,任务的点数等于其中已解决的子任务的数量。此外,如果Polycarp完全解决了某个任务(解决了所有k个子任务),他会收到一个额外的点数。因此,他完整解决某个任务获得的总点数是k+1。 
  
Polycarp有M分钟的时间。他可以获得的最高分数是多少? 

 



输入:

第一行包含三个整数n,k,和M1n≤451k≤450M≤2·10^9)。

第二行包含ķ整数数字,值tj1tj≤ 1000000),其中tj是解决j个子任务需要时间tj。

输出:

打印Polycarp可以在M分钟内获得的最大分数。

示例输入:

2 4 11
1 2 3 4

示例输出:

6

提示:

参考答案(内存最优[1120]):

#include<stdio.h>
#include<algorithm>
using namespace std;
long long int n,k,m;
long long int a[50];
long long int sum;
long long int maxi;
long long int max(long long int x,long long int y)
{
	return x>y?x:y;
}
long long int dfs(long long int v,long long int pon)//×°µÄ¸öÊý,×°µÄ½ïÊý 
{
	long long int weight=pon;
	long long int value=v*(k+1);//ÏÖÔڵļÛÖµ 
	for(long long int i=0;i<k;i++)//±íʾµÚi¸öÎïÆ· 
	{
		long long int j;
		j=(m-weight)/a[i];
		if(j+v>n)
		{
			j=n-v;
		}
		if(j>=0)
		{
			weight+=a[i]*j;
			value+=j;
		}
	}
	return value;
}
int main()
{
	scanf("%lld %lld %lld",&n,&k,&m);
	for(long long int i=0;i<k;i++)
	{
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	sort(a,a+k);
	for(long long int l=0;l<=n&&sum*l<=m;l++)
	{
		maxi=max(maxi,dfs(l,sum*l));
	}
	printf("%lld",maxi);
}

参考答案(时间最优[3]):

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100;
ll a[maxn];
int main()
{
    int n,k;
    ll m;
    scanf("%d%d%lld",&n,&k,&m);
    ll sum=0;
    for(int i=0;i<k;i++)
    {
        scanf("%lld",&a[i]);
        sum+=a[i];
    }
    sort(a,a+k);
    ll maxx=0;
    for(int i=0;i<=n&&m>=i*sum;i++)
    {
        ll sum1=m-i*sum;
        ll gra=i*(k+1);
        for(int j=0;j<k;j++)
        {
            for(int l=1;l<=n-i;l++)
            {
                if(sum1>=a[j])
                {
                    sum1-=a[j];
                    gra++;
                }
            }
        }
        maxx=max(gra,maxx);
    }
    printf("%lld\n",maxx);
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。