題意:
給定n個物品，每個物品具有權(quán)值a[i]，在這些物品里選出若干個物品，使得權(quán)值和>=k，就說是一個合法的方案。對于一個物品，如果存在一個合法的方案，在這個方案中去掉它以后方案就變成不合法了，就說這個物品是“必要的”。求有多少個物品是必要的。
n<=5000,k<=5000
思路: 如果a[i]>=k，一定必要，因為存在只包含他自己的方案，去掉他就不合法了。對于a[i]<k，如果其他物品能夠湊出一個方案，權(quán)值和在[k-a[i],k-1]之間，該物品同樣是必要的。所以想到一種樸素的想法，就是去掉某一個物品，然后依次進行01背包。但是這樣很lao，因為時間復雜度會達到n * n * k. 可以用可逆背包鏈接
或者用一種預(yù)處理前綴后綴背包的手法，比如說dp[i][j]表示前i個物品，能否湊出j。dp2[i][j]表示從n到i這些物品，能否湊出j.
預(yù)處理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這種運行慢的語言可能會被卡掉。
所以想到了用前綴和優(yōu)化，我們還是枚舉l，但是r不用二分了。sum[i][j]存dp2某一行的前綴和，表示用n到i這些數(shù)，和<=j的方案數(shù)。
根據(jù)左側(cè)數(shù)j的大小，分情況討論右側(cè)x的范圍?？梢园l(fā)現(xiàn)這兩種情況的方案數(shù)分別對應(yīng)了sum[i+1][k-1-j]和sum[i+1][k-1-j] - sum[i+1][k-a[i]-j-1]，這就是前綴和的魅力。如果不是很理解，建議仔細思考一下sum數(shù)組是這些數(shù)能湊出<=j的方案數(shù)，用能湊出<=10的方案數(shù)減去<=5的方案數(shù)，就是湊出的值在[6,10]之間的方案數(shù)了。
時間復雜度: O(nk*log(k))或O(nk)
代碼:
二分版:文章來源：http://www.zghlxwxcb.cn/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
*/
前綴和版:文章來源地址http://www.zghlxwxcb.cn/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的方案數(shù)，方便統(tǒng)計方案
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個數(shù)能否湊出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];
}
}
//問題轉(zhuǎn)化為對于每個a[i]，如果a[i]>=k，那么肯定符合，因為存在一種只有它自己的方案，它不可或缺
//；否則的話，如果存在某種方案坐落在[k-a[i],k-1]之間，a[i]同樣符合
for(int i=1;i<=n;++i) //枚舉當前的數(shù)
{
for(int j=0;j<k;++j) //枚舉前i-1個數(shù)的和
{
if(!dp[i][j]) continue;
int l = k-a[i]-j;
int r = k-1-j;
int cnt = 0;//右邊需要湊的方案數(shù)量
if(j>=k-a[i]) //l<=0
{
//j+x<=k-1, x<=k-1-j
cnt = sum[i+1][r]; //右邊，<=k-1-j的方案數(shù)
}
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的方案數(shù)
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
*/
到了這里，關(guān)于有一些東西必不可少（前后背包+二分/前綴和優(yōu)化）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
