Math Show
时间： 1ms 内存：128M
描述：
Polycarp参加数学展。他被赋予n个任务，每个任务由k个子任务组成，编号为1到k。他花了tj分钟来解决任何任务的第j个子任务。因此，解决子任务所需的时间仅取决于其索引，而不取决于任务本身。Polycarp可以按任何顺序解决子任务。
解决了任意问题的子任务，他都能获得了一分。因此，任务的点数等于其中已解决的子任务的数量。此外，如果Polycarp完全解决了某个任务（解决了所有k个子任务），他会收到一个额外的点数。因此，他完整解决某个任务获得的总点数是k+1。
Polycarp有M分钟的时间。他可以获得的最高分数是多少？
输入：
第一行包含三个整数n,k,和M（1≤n≤45，1≤k≤45，0≤M≤2·10^9）。
第二行包含ķ整数数字，值tj（1≤tj≤ 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;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。