本题为完全背包稍微变形,主要是理解脑力耗尽后会完全恢复,即再开一次背包(只会恢复一次,如果可以无限恢复的话就无解了),在开第二次背包时,视频的内容量减半而经验增倍。总结来说就是开两次背包,第二次背包时注意视频内容量和经验的变化。

int main() {
    int m,n,sum,temp;
    cin >> m >> n;
    for (int i = 1; i <= m; i++) {
    	cin >> v[i] >> w[i];
	}
	for (int i = 1; i <= m; i++) {
		for (int j = w[i]; j <= n; j++) {
			f[j] = max(f[j], f[j - w[i]] + v[i]);
		}
	}
	temp = f[n];
	memset(f,0,sizeof(f));
	for (int i = 1; i <= m; i++) {
		w[i] = w[i] / 2;
		v[i] = v[i] * 2;
	}
	for (int i = 1; i <= m; i++) {
		for (int j = w[i]; j <= n; j++) {
			f[j] = max(f[j], f[j - w[i]] + v[i]);
		}
	}
	sum = temp + f[n];
        cout << sum;
	return 0;
} 

0 comments

No comments so far...