1 solutions
-
0
本题为完全背包稍微变形,主要是理解脑力耗尽后会完全恢复,即再开一次背包(只会恢复一次,如果可以无限恢复的话就无解了),在开第二次背包时,视频的内容量减半而经验增倍。总结来说就是开两次背包,第二次背包时注意视频内容量和经验的变化。
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; }
- 1
Information
- ID
- 16
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 10
- Tags
- # Submissions
- 8
- Accepted
- 4
- Uploaded By