1 solutions

  • 0
    @ 2021-10-14 14:05:27

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

    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