- 题解
P1015 认真学习的一天 题解
- 2021-10-14 13:43:39 @
本题为完全背包稍微变形,主要是理解脑力耗尽后会完全恢复,即再开一次背包(只会恢复一次,如果可以无限恢复的话就无解了),在开第二次背包时,视频的内容量减半而经验增倍。总结来说就是开两次背包,第二次背包时注意视频内容量和经验的变化。
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...