總結(jié)：
1.

?

50分的代碼（因?yàn)橛啥鄠€數(shù)據(jù)，所以不能改變num[]數(shù)組）

#include<bits/stdc++.h> using namespace std; struct node{int pos, value; }que[1005]; int c[1005], w[1005], num[1005], f[1005], vis[1005]; int n, head, tail, V, q, h, z[1005]; int main() {cin >> n;for(int i = 0; i < n; i++)cin >> c[i] >> w[i] >> num[i];cin >> q;for(int cnt = 1; cnt <= q; cnt++) { memset(f, 0, sizeof(f));cin >> h >> V;vis[h] = 1;for(int i=0;i<n;i++) {if(!vis[i]){z[i] = min(num[i], V/c[i]); //用z[]數(shù)組代表能用多少件物品for(int mo=0;mo<c[i];mo++) {head=tail=0;for(int k=0;k<=(V-mo)/c[i];k++) {int x=k;int y=f[k*c[i]+mo]-k*w[i];while(head<tail && que[head].pos<k-z[i])head++;while(head<tail && que[tail-1].value<=y)tail--;que[tail].value=y,que[tail].pos=x;tail++;f[k*c[i]+mo]=que[head].value+k*w[i];}}} } cout << f[V] << endl; vis[h] = 0; } return 0; }

?

正解

#include<bits/stdc++.h> using namespace std; long long n, q, d, e, ans, vis[1010]; long long dp[1010][1010], f[1010][1010], val[1010], w[1010], c[1010]; long long re,p; void pre() {for(int i = 1; i <= n; i++){for(int j = 1; j <= 1000; j++)dp[i][j] = dp[i-1][j];re = c[i]; p = 1;while(re>=p){for(int j=1000;j>=w[i]*p;j--)dp[i][j]=max(dp[i][j],dp[i][j-w[i]*p]+val[i]*p);re-=p;p=p<<1;}if(re){for(int j=1000;j>=w[i]*re;j--)dp[i][j]=max(dp[i][j],dp[i][j-w[i]*re]+val[i]*re);}}for(int i = n; i >= 1; i--){for(int j = 1; j <= 1000; j++)f[i][j] = f[i+1][j];re = c[i]; p = 1;while(re>=p){for(int j=1000;j>=w[i]*p;j--)f[i][j]=max(f[i][j], f[i][j-w[i]*p]+val[i]*p);re-=p;p=p<<1;}if(re){for(int j=1000;j>=w[i]*re;j--)f[i][j]=max(f[i][j],f[i][j-w[i]*re]+val[i]*re);}} }int main() {cin >> n;for(int i = 1; i <= n; i++)cin >> w[i] >> val[i] >> c[i];pre();cin >> q;while(q--){ans = 0;cin >> d >> e;d++;for(int i = 0; i <= e; i++)ans = max(ans, dp[d-1][i]+f[d+1][e-i]);cout << ans << endl;} return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/lovezxy520/p/11374675.html

總結(jié)

以上是生活随笔為你收集整理的【题解】lugu P4095 Eden的新背包问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。