题意:
给定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)
代码:
二分版:

#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 210 4 3 10 2
*/

前缀和版:

#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-jcnt = 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
*/