小A在刷题题解

题目链接

小A在刷题

前置知识

分组背包

题意

本来，这是一道非常普通的完全背包问题。但题目中有一个奇怪的条件：

现在小X第 \(i\) 次刷题时，所获得的经验值会乘上一个系数 \(f_i\)。具体地说，当小X第 \(i\) 次刷题选择刷第 \(j\) 道题时，他消耗 \(w_j\) 点精力，获得\(v_j \times f_i\)点经验值。当然，他也可以在第 \(i\) 次选择时选择休息（即轮空），消耗 \(0\) 点精力，获得 \(0\) 点经验值。

也就是说，原来，无论如何，物品的价值是不会改变的。但现在，随着选择物品的个数的改变，物品的价值也会改变。那么，如何用背包问题的思路来解决这道题呢？

分析

其实，遇到这一类不是很板子的背包问题时，我们往往会考虑使用分组背包的思路。

这道题也是类似的。我们把 每一次选择 看成一组物品，每一组物品相对于原来而言，体积不变，价值乘上系数 \(f_i\)。

为什么使用分组背包呢？因为这样的话，我们可以保证，每次选择都只选择一件物品，同时物品的体积和价值也满足了题目的要求。而且，分组背包可以在每一组当中不选择任何物品，这不正好满足了题目的轮空要求吗？

综上所述，我们使用分组背包的思路是完全可行的，同时，时间复杂度为 \(\Theta(nms)\)，也符合题目要求。

实现

实现并不是很复杂，就是一个分组背包的板子。

#include 
#include 
#include 

inline int max(int a,int b) {return a > b ? a : b;}

inline int read(){
	int t = 0,flag = 1;
	register char c = getchar();
	while (c < 48 || c > 57) {if (c == '-') flag = -1;c = getchar();}
	while (c >= 48 && c <= 57) t = (t << 1) + (t << 3) + (c ^ 48),c = getchar();
	return flag * t;
}//快读，可忽略

int n,m,s,f[201],w[201],v[201],dp[1001];

int main(){
	n = read(),m = read(),s = read();//读入，等价于scanf("%d %d %d",&n,&m,&s); 也等价于cin >> n >> m >> s;下不再赘述
	for (int i = 1;i <= m;i++) f[i] = read();
	for (int i = 1;i <= n;i++) w[i] = read(),v[i] = read();
	for (int i = 1;i <= m;i++){
		for (int j = s;j >= 0;j--){
			for (int k = 1;k <= n;k++){//三层循环，注意顺序
				if (j < w[k]) continue;
				dp[j] = max(dp[j],dp[j - w[k]] + f[i] * v[k]);
				
			}
		}
	}
	printf("%d\n",dp[s]);//输出答案
	return 0;
}

完结撒花??ヽ(°▽°)ノ?。