p6433「EZEC-1」出题

题目背景

你是一个毒瘤出题人。

题目描述

已知你有 n 道毒瘤题，已经出好了题面，但数据还没出好。你还剩下 m 的时间，每道题的毒瘤程度为 a**i，出数据的时间是 x*i，你有 k* 个老师，每个老师珂以把一道题的毒瘤程度翻倍（每道题目最多被翻倍一次）。你的父母由于坚决反对你出公开赛，抢走了你的一道题，现在老师和父母的行动你都可以控制，但每位老师和父母的行为必须执行，请问你要怎么做，才能使出的题毒瘤程度之和最大？

输入格式

第一行三个整数：n,m,k。

接下来 n 行，每行 2 个整数，分别是 ai,xi*。

输出格式

一个整数，最大的毒瘤程度之和。

输入输出样例

输入 #1

1
2
3
4
3 10 1
6 9
7 2
1 8

输出 #1

1
15

输入 #2

1
2
3
4
5
6
5 20 2
5 3 
9 7
2 6
7 8
1 2

输出 #2

1
38

输入 #3

1
2
3
4
3 6 2
5 4
3 3
3 3

输出 #3

1
12

题解

用 $dp[i][j]$ 表示用 i 时间，使用 j 次翻倍后可以得到的最大毒瘤值

如果所有时间和 小于等于 m，就是一个贪心…比赛的时候想大于是贪心，菜哭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const int MAX=100+10;
int n,m,k,a[MAX],x[MAX],ans=0,sum=0;
int f[1010][MAX];
bool cmp(int x,int y){
	return x>y;
}
int main(){
	//freopen("in","r",stdin);
	sf(n);sf(m);sf(k);
	fi(i,0,n){
		sf(a[i]);sf(x[i]);
		sum += x[i];
	}
	if(sum<=m){
		sort(a,a+n,cmp);
		fi(i,0,k) ans += a[i]*2;
        fi(i,k,n-1) ans += a[i];
		pf(ans); 
		return 0;
	}
	fi(i,0,n)
		fd(j,m+1,x[i]){
			f[j][0]=max(f[j][0],f[j-x[i]][0]+a[i]);
			ans = max(ans,f[j][0]);
			for(int h = 1;h<=min(k,i+1);h++){
				f[j][h] =max(f[j][h],max(f[j-x[i]][h] + a[i],f[j-x[i]][h-1] + 2*a[i])); 
				ans = max(ans,f[j][h]);
			}
		}
	pf(ans);
	return 0;
}