思路
得到分数最多的状态可表示为做完 $x$ 张卷子, 然后在剩下的 $n-x$张卷子中做了 $y$ 道题目。
可以对 $x$ 进行枚举, 做完 $x$ 张卷子可能会有一些剩余时间,尽可能做花费时间少的题目就可以使得分数最大化。
时间复杂度: $O(n*k)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int n,k,m;
int t[50];
int ans,tot;
int main()
{
cin>>n>>k>>m;
for(int i=1;i<=k;i++){
cin>>t[i];
tot += t[i];
}
sort(t+1,t+1+k);
for(int i=0;i<=n;i++){
int cost = i*tot,cur = i*(k+1);
if(cost>m) break;
int ni = n-i;
for(int j=1;j<=k;j++){
if(cost+(n-i)*t[j]<=m){
cur += n-i;
cost += (n-i)*t[j];
}else{
cur += (m-cost)/t[j];
break;
}
}
ans = max(ans,cur);
}
cout<<ans;
}