题意:
给定n个物品，每个物品具有权值a[i]，在这些物品里选出若干个物品，使得权值和>=k，就说是一个合法的方案。对于一个物品，如果存在一个合法的方案，在这个方案中去掉它以后方案就变成不合法了，就说这个物品是“必要的”。求有多少个物品是必要的。
n<=5000,k<=5000
思路: 如果a[i]>=k，一定必要，因为存在只包含他自己的方案，去掉他就不合法了。对于a[i]<k，如果其他物品能够凑出一个方案，权值和在[k-a[i],k-1]之间，该物品同样是必要的。所以想到一种朴素的想法，就是去掉某一个物品，然后依次进行01背包。但是这样很lao，因为时间复杂度会达到n * n * k. 可以用可逆背包链接
或者用一种预处理前缀后缀背包的手法，比如说dp[i][j]表示前i个物品，能否凑出j。dp2[i][j]表示从n到i这些物品，能否凑出j.
预处理dp之后，对于每个物品i，看是否存在dp[i-1][l]和dp[i+1][r]，他们都是合法方案，且满足 k-a[i]<=l+r<=k-1.
显然枚举l、r很慢，但是可以只枚举l，另一个通过二分得到。
枚举l，此时r满足k-a[i]-l<=r，lower_bound得到r的左边界，之后判断r是否满足r<=k-1-l，即可判断是否存在合法方案。
但是这样带一个log，像python这种运行慢的语言可能会被卡掉。
所以想到了用前缀和优化，我们还是枚举l，但是r不用二分了。sum[i][j]存dp2某一行的前缀和，表示用n到i这些数，和<=j的方案数。
根据左侧数j的大小，分情况讨论右侧x的范围。可以发现这两种情况的方案数分别对应了sum[i+1][k-1-j]和sum[i+1][k-1-j] - sum[i+1][k-a[i]-j-1]，这就是前缀和的魅力。如果不是很理解，建议仔细思考一下sum数组是这些数能凑出<=j的方案数，用能凑出<=10的方案数减去<=5的方案数，就是凑出的值在[6,10]之间的方案数了。
时间复杂度: O(nk*log(k))或O(nk)
代码:
二分版:文章来源：https://www.toymoban.com/news/detail-714804.html
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 5002;
int n,m,k,T;
bool dp[N][N];
bool dp2[N][N];
int b[N];
int a[N];
int main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>m>>k;
n = 0;
int ans = 0;
for(int i=1;i<=m;++i)
{
cin>>b[i];
if(b[i]>=k) ans++;
else a[++n] = b[i];
}
dp[0][0] = 1;
dp2[n+1][0] = 1;
for(int i=1;i<=n;++i)
{
for(int j=0;j<=k;++j)
{
dp[i][j] |= dp[i-1][j];
if(j>=a[i]) dp[i][j] |= dp[i-1][j-a[i]];
}
}
for(int i=n;i>=1;--i)
{
for(int j=0;j<=k;++j)
{
dp2[i][j] |= dp2[i+1][j];
if(j>=a[i]) dp2[i][j] |= dp2[i+1][j-a[i]];
}
}
// cout<<dp2[5][2]<<"!\n";
for(int i=1;i<=n;++i)
{
// cout<<i<<":"<<a[i]<<"?\n";
vector<int> l,r;
for(int j=0;j<=k;++j)
{
if(dp[i-1][j]) l.push_back(j);
if(dp2[i+1][j])
{
r.push_back(j);
}
}
bool flag = 0;
int idx1 = lower_bound(l.begin(),l.end(),k-a[i]) - l.begin();
int idx2 = lower_bound(r.begin(),r.end(),k-a[i]) - r.begin();
if(idx1!=l.size() && l[idx1] <= k-1)
{
flag = 1;
// cout<<i<<":"<<"?\n";
}
if(idx2!=r.size() && r[idx2] <= k-1)
{
flag = 1;
// cout<<i<<" "<<idx2<<":"<<r[idx2]<<"?\n";
// cout<<i<<":"<<"??\n";
// for(auto item:r) cout<<item<<"???\n";
}
// cout<<i<<":"<<flag<<"?\n";
for(int j=l.size()-1;!flag && j>=0;--j)
{
int now = l[j];
int idx = lower_bound(r.begin(),r.end(),k-a[i]-l[j]) - r.begin();
if(idx!=r.size() && now + r[idx] <= k-1) flag = 1;
}
if(flag) ans ++ ;
}
cout<<ans;
return 0;
}
/*
6 20
10 4 3 10 25 2
10 4 3 10 2
*/
前缀和版:文章来源地址https://www.toymoban.com/news/detail-714804.html
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 5002;
int n,m,k,T;
bool dp[N][N];
bool dp2[N][N];
int b[N];
int a[N];
int sum[N][N]; //从n到i，<=j的方案数，方便统计方案
int main(void)
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>m>>k;
n = 0;
int ans = 0;
for(int i=1;i<=m;++i)
{
cin>>b[i];
if(b[i]>=k) ans++;
else a[++n] = b[i];
}
//从前向后dp、从后向前dp，求前i个数能否凑出j、从n到i能否凑出j
dp[0][0] = 1;
dp2[n+1][0] = 1;
for(int i=1;i<=n;++i)
{
for(int j=0;j<=k;++j)
{
dp[i][j] |= dp[i-1][j];
if(j>=a[i]) dp[i][j] |= dp[i-1][j-a[i]];
}
}
for(int i=n;i>=1;--i)
{
for(int j=0;j<=k;++j)
{
dp2[i][j] |= dp2[i+1][j];
if(j>=a[i]) dp2[i][j] |= dp2[i+1][j-a[i]];
if(j==0) sum[i][j] = 1;
else sum[i][j] = sum[i][j-1] + dp2[i][j];
}
}
//问题转化为对于每个a[i]，如果a[i]>=k，那么肯定符合，因为存在一种只有它自己的方案，它不可或缺
//；否则的话，如果存在某种方案坐落在[k-a[i],k-1]之间，a[i]同样符合
for(int i=1;i<=n;++i) //枚举当前的数
{
for(int j=0;j<k;++j) //枚举前i-1个数的和
{
if(!dp[i][j]) continue;
int l = k-a[i]-j;
int r = k-1-j;
int cnt = 0;//右边需要凑的方案数量
if(j>=k-a[i]) //l<=0
{
//j+x<=k-1, x<=k-1-j
cnt = sum[i+1][r]; //右边，<=k-1-j的方案数
}
else //l>0
{
//j+x>=k-a[i],x>=k-a[i]-j
//j+x<=k-1,x<=k-1-j
//求k-a[i]-j<=x<=k-1-j的方案数
cnt = sum[i+1][r] - sum[i+1][l-1];
}
if(cnt>0)
{
ans ++ ;
break;
}
}
}
cout<<ans;
return 0;
}
/*
6 20
10 4 3 10 25 2
*/
到了这里，关于有一些东西必不可少（前后背包+二分/前缀和优化）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
