整理了 NOIP 与某些省份省选的背包题。
NOIP 的背包题
[NOIP 2006 提高组] 金明的预算方案
树形背包似乎也是可做的，但是由于最多有两个附件，并且是分为两类，也就是附件不会再有附件，这个问题就成了最简单的背包问题了。
我们对于所有主件跑背包，在决策中分类讨论只买主件，买一个附件，都买的最少一种，最多四种情况就行了。
为什么是绿？
代码↓
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=1e5+115;
int w[MN][3], v[MN][3], dp[MN];
int n, m;
signed main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin>>n>>m;for(int i=1; i<=m; ++i){int rv, rw, type;cin>>rv>>rw>>type;if(type==0){w[i][0]=rw;v[i][0]=rv;}else{if(w[type][1]==0){w[type][1]=rw;v[type][1]=rv;}else{w[type][2]=rw;v[type][2]=rv;}}}for(int i=1; i<=m; ++i){for(int j=n; j>=0; --j){//买主if(j-v[i][0]>=0){dp[j]=max(dp[j],dp[j-v[i][0]]+v[i][0]*w[i][0]);}//买主和1if(j-v[i][0]-v[i][1]>=0){dp[j]=max(dp[j],dp[j-v[i][0]-v[i][1]]+v[i][0]*w[i][0]+v[i][1]*w[i][1]);}//买主和2if(j-v[i][0]-v[i][2]>=0){dp[j]=max(dp[j],dp[j-v[i][0]-v[i][2]]+v[i][0]*w[i][0]+v[i][2]*w[i][2]);}//买主和1和2if(j-v[i][0]-v[i][1]-v[i][2]>=0){dp[j]=max(dp[j],dp[j-v[i][0]-v[i][1]-v[i][2]]+v[i][0]*w[i][0]+v[i][1]*w[i][1]+v[i][2]*w[i][2]);}}}int ans=0;for(int i=0; i<=n; ++i){ans=max(ans,dp[i]);}cout<<ans<<'\n';return 0;
}
[NOIP 2014 提高组] 飞扬的小鸟
提高组里边三个背包中最神经病的，一大堆细节，恶心死我了。
首先正常的 \(O(n^3)\) 级别的 dp 是非常好想的，可以拿到 70pts。
但是这个样子显然是不行的，考虑优化。
发现可以抽象成对于每一个横坐标做一次只有一个物品的完全背包，特殊处理一下上边界，之后在处理向下的情况，优化成功。
和 AI 一起调半天......
代码↓
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int n, m, k, down[10100], up[10100];
int x[10100], y[10100];
int dp[10100][1010], sum[10100];
bool pip[10100];
void Read(){cin>>n>>m>>k;for(int i=0; i<=n; ++i) down[i]=1, up[i]=m+1;for(int i=0; i<n; ++i) cin>>x[i]>>y[i];for(int i=1; i<=k; ++i){int pos, hg, lw; cin>>pos>>lw>>hg;down[pos]=lw+1; up[pos]=hg-1;sum[pos]++; pip[pos]=true;}for(int i=1; i<=n; ++i) sum[i]+=sum[i-1];
}
void Dp(){memset(dp,0x3f,sizeof(dp));for(int i=1; i<=m; ++i){dp[0][i]=0;}//以上是初始化for(int i=1; i<=n; ++i){for(int j=x[i-1]+1; j<=m; ++j){dp[i][j]=min(dp[i][j],dp[i-1][j-x[i-1]]+1);dp[i][j]=min(dp[i][j],dp[i][j-x[i-1]]+1);}for(int j=m-x[i-1]; j<=m; ++j){dp[i][m]=min(dp[i][m],dp[i-1][j]+1);dp[i][m]=min(dp[i][m],dp[i][j]+1);}for(int j=1; j<=m-y[i-1]; ++j){dp[i][j]=min(dp[i][j],dp[i-1][j+y[i-1]]);}for(int j=0; j<down[i]; ++j) dp[i][j]=0x3f3f3f3f;for(int j=up[i]+1; j<=m; ++j) dp[i][j]=0x3f3f3f3f;}
}
void Getans(){int ans=0x3f3f3f3f;for(int i=down[n]; i<=up[n]; ++i){ans=min(ans,dp[n][i]);}if(ans!=0x3f3f3f3f){cout<<1<<'\n'<<ans<<'\n';}else{cout<<0<<'\n';for(int i=n-1; i>=0; --i){for(int j=1; j<=m; ++j){if(dp[i][j]<0x3f3f3f3f){cout<<sum[i]<<'\n';return;}}}cout<<0<<'\n';}
}
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);Read(); Dp(); Getans();return 0;
}
[NOIP 2018 提高组] 货币系统
矛盾是复杂的，问题是简单的。
我们似乎没有办法直接确认更好的货币系统，那么换个思路，我们可以尝试去清除不需要的面值。
什么面值是不需要的？就是能被别的给表示出来的。
跑计数背包就行的。
代码↓
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int MN=55555;
int dp[MN], n, a[MN];
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T; cin>>T; while(T--){memset(dp,0,sizeof(dp));cin>>n; for(int i=1; i<=n; ++i) cin>>a[i];for(int i=1; i<=n; ++i) dp[a[i]]=1;for(int i=1; i<=n; ++i){for(int j=a[i]; j<MN; ++j){dp[j]+=dp[j-a[i]];}}int ans=0;for(int i=1; i<=n; ++i){ans+=(dp[a[i]]==1);}cout<<ans<<'\n';}return 0;
}