CF846B 思维

题意

有n个任务,每个任务有相同的k个子任务,你可以按任何顺序完成子任务,每完成一个得1分,但如果你把一个任务的所有子任务都完成了,就可以额外的得到一分.每个子任务所需要的时间$ t_i \leq 10^6$, 你有M的时间,求你最多能得多少分.

$n \leq 45,k \leq 45, M \leq 2*10^9 $

分析

问题的难点在于究竟要不要完成一个完整的任务.

比如说这样一组数据.

2 4 17
1 2 4 7

如果我们选择完成一个完整的任务,可以获得7分,否则可以获得6分.

难点在完成多少个完整的任务上,那么我们是不是就可以枚举这个东西呢,其他的当做不完成 完整的拿来贪心

复杂度 $ O(n^2k)$

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=47;
int a[MAXN];
int t[MAXN][MAXN];
int main(){
	int n,k,M;scanf("%d%d%d",&n,&k,&M);
	int sum=0;
	for(int i=0;i<k;++i)scanf("%d",&a[i]),sum+=a[i];
	sort(a,a+k);
	for(int i=0;i<n;++i)
		for(int j=0;j<k;++j)
			t[i][j]=a[j];//n row k col
	int ans=0;
	for(int full=0;full<=n;++full){
		int tmp=M;
		int res=full*(k+1);
		tmp-=sum*full;//the remain time
		if(tmp<0)break;
		for(int j=0;j<k-1;++j){
			for(int i=full;i<n;++i){
				if(tmp>=t[i][j])tmp-=t[i][j],res++;
				else goto flag;
			}
		}
		flag:
		if(res>ans){
			ans=res;
		}
	}
	printf("%d\n",ans);
	return 0;
}