题目链接:https://ac.nowcoder.com/acm/contest/46812/D
思路:01背包,当要从一段物品中选一件出来,可以像前缀和和后缀和一样,进行前缀dp和后缀dp。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
long long dp[N],dpp[N];
long long pre[N][N],suf[N][N];
long long cnt[N];
int w[N],v[N];
int main(){
int n,m;
cin>>n>>m;
cnt[0] = 1;
for (int i=1;i<=n;i++) cin>>v[i]>>w[i];
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
pre[i][j] = pre[i-1][j];
if (j>=v[i]) pre[i][j] = max(pre[i][j],pre[i-1][j-v[i]]+w[i]);
}
}
for (int i=n;i>=1;i--){
for (int j=1;j<=m;j++){
suf[i][j] = suf[i+1][j];
if (j>=v[i]) suf[i][j] = max(suf[i][j],suf[i+1][j-v[i]]+w[i]);
}
}
for (int k=1;k<=n;k++){
long long val = 0,val2 = 0;
for (int i=0;i<=m;i++){
val = max(val,pre[k-1][i]+suf[k+1][m-i]);
if (m-v[k]>=i) val2 = max(val2,pre[k-1][i]+w[k]+suf[k+1][m-v[k]-i]);
}
long long ans = max(0LL,val+1-val2);
cout<<ans<<'\n';
}
return 0;
}
标签:pre,suf,int,max,训练营,long,牛客,2023,dp
From: https://www.cnblogs.com/xjwrr/p/17268468.html