标签：pre suf 01 int max 多校 long 背包
0x1f 题目：
0x2f 题意：
- 定义初始背包的最优解\(V_{max}\)
- 定义n个物品去掉任意一个后，最优解为\(V_{max}'\)
- 每一个物品\(w[i],v[i]\)，在\(v[i]\)上加上一个最小值，使得\(V_{max}\) > \(V_{max}'\)
- 背包的容量是m
0x3f 思路：
- 前缀背包：$pre[ i ][ j ] $ 表示前 \(i\) 个物品使用体积为 \(j\) 的最大价值
- 后缀背包：\(suf[ i ][ j ]\) 表示 \(i\) 之后物品使用体积为 \(j\) 的最大价值（转移的方法和01背包一样）
- 接下来贪心考率在什么情况下\(V_{max}\) > \(V_{max}'\)
- 计算\(V_{max}'\)：\(\max _{0 \to m}^j (pre[i-1][j] + suf[i+1][m-j])\)
- 要让\(V_{max}\) > \(V_{max}'\)成立，可以在背包里提前预留\(w[i]\)，计算出最大值，要让物品\(i\)成为必需品，至少需要加上 \(V_{max}\) + 1 - \(（V_{max}' + v[i]）\)
- 为什么？因为贪心结果是必须把物品 \(i\) 放入背包的，只有这一个物品，容易贪心留\(w[i]\)的空间是最优的
- 计算预留\(w[i]\)空间：\(\max _{0 \to m - w[i]}^j (pre[i-1][j] + suf[i+1][m-j-w[i]])\)
0x4f 代码：
#include<bits/stdc++.h>
#define debug1(a) cout<<#a<<'='<< a << endl;
#define debug2(a,b) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<endl;
#define debug3(a,b,c) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<" "<<#c<<" = "<<c<<endl;
#define debug4(a,b,c,d) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<" "<<#c<<" = "<<c<<" "<<#d<<" = "<<d<<endl;
#define debug5(a,b,c,d,e) cout<<#a<<" = "<<a<<" "<<#b<<" = "<<b<<" "<<#c<<" = "<<c<<" "<<#d<<" = "<<d<<" "<<#e<<" = "<<e<<endl;
#define endl "\n"
#define fi first
#define se second
#define caseT int T;cin >> T;while(T--)
#define int long long
//#define int __int128
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC optimize(2)
inline int rd()
{
int f=1,x=0;char c=getchar();
while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return f*x;
}
//常数定义
const double eps = 1e-6;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int N = 5010;
void solve(){
int n, m; cin >> n >> m;
vector<int>w(n), v(n);
for(int i = 0; i < n; ++i) {
cin >> w[i] >> v[i];
}
vector<vector<LL>> pre(n, vector<LL>(m + 1));
vector<vector<LL>> suf(n, vector<LL>(m + 1));
for(int i = 0; i < n; ++i) {
if(i) pre[i] = pre[i - 1];
for(int j = m; j >= w[i]; --j) {
pre[i][j] = max(pre[i][j], pre[i][j - w[i]] + v[i]);
}
}
for(int i = n - 1; i >= 0; --i) {
if(i < n - 1) suf[i] = suf[i + 1];
for(int j = m; j >= w[i]; --j) {
suf[i][j] = max(suf[i][j], suf[i][j - w[i]] + v[i]);
}
}
for(int i = 0; i < n; ++i) {
LL max1 = 0, max2 = 0;
for(int j = 0; j <= m; ++j) {
max1 = max(max1, (i ? pre[i - 1][j] : 0) + (i + 1 < n ? suf[i + 1][m - j] : 0));
}
for(int j = 0; j <= m - w[i]; ++j) {
max2 = max(max2, (i ? pre[i - 1][j] : 0) + (i + 1 < n ? suf[i + 1][m - j - w[i]] : 0));
}
cout << max(0LL, max1 + 1 - v[i] - max2) << "\n";
}
}
signed main()
{
/*
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
*/
//caseT
solve();
return 0;
}
/*
*/
标签：pre,
suf,
01,
int,
max,
多校,
long,
背包
From： https://www.cnblogs.com/cfddfc/p/17077485.html