背包 dp 歷年真題：做題記錄
整理了 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]);
}
//買主和1
if(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]);
}
//買主和2
if(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和2
if(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 提高組] 飛揚的小鳥
提高組里邊三個背包中最神經(jīng)病的，一大堆細節(jié)，惡心死我了。
首先正常的 \(O(n^3)\) 級別的 dp 是非常好想的，可以拿到 70pts。
但是這個樣子顯然是不行的，考慮優(yōu)化。
發(fā)現(xiàn)可以抽象成對于每一個橫坐標做一次只有一個物品的完全背包，特殊處理一下上邊界，之后在處理向下的情況，優(yōu)化成功。
和 AI 一起調(diào)半天......
代碼↓
點擊查看代碼
#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 提高組] 貨幣系統(tǒng)
矛盾是復雜的，問題是簡單的。
我們似乎沒有辦法直接確認更好的貨幣系統(tǒng)，那么換個思路，我們可以嘗試去清除不需要的面值。
什么面值是不需要的？就是能被別的給表示出來的。
跑計數(shù)背包就行的。
代碼↓
點擊查看代碼
#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;
}
省選的背包題
[HEOI2013] Eden 的新背包問題
我們?nèi)ビ^察下背包的式子，發(fā)現(xiàn) dp 的階段就是考慮前 i 個物品。
我們從前往后和從后往前跑 dp, 到時候直接拼起來前后綴就行了。
代碼↓
點擊查看代碼
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, tottt;
int dp_pre[10001][1001], dp_suf[10001][1001];
struct Node{
int id, v, w;
}node[114514];
int l[114514], r[114514];
void Read(){
cin>>n;
for(int i=1; i<=n; ++i){
int rw, rv, rm;
cin>>rw>>rv>>rm;
l[i]=tottt+1;
for(int j=1; j<=rm; j<<=1){
node[++tottt].w=rw*j;
node[tottt].v=rv*j;
node[tottt].id=i;
rm-=j;
}
if(rm){
node[++tottt].w=rw*rm;
node[tottt].v=rv*rm;
node[tottt].id=i;
}
r[i]=tottt;
}
}
void Do_dp(){
for(int i=1; i<=tottt; ++i){
for(int j=0; j<=1000; ++j) dp_pre[i][j]=dp_pre[i-1][j];
for(int j=1000; j>=node[i].w; --j){
dp_pre[i][j]=max(dp_pre[i][j],dp_pre[i-1][j-node[i].w]+node[i].v);
}
}
for(int i=tottt; i>=1; --i){
for(int j=0; j<=1000; ++j) dp_suf[i][j]=dp_suf[i+1][j];
for(int j=1000; j>=node[i].w; --j){
dp_suf[i][j]=max(dp_suf[i][j],dp_suf[i+1][j-node[i].w]+node[i].v);
}
}
}
void Solve(){
int q; cin>>q;
for(int i=1; i<=q; ++i){
int pos, ask, ans=0;
cin>>pos>>ask; ++pos;
for(int j=0; j<=ask; ++j){
ans=max(ans,dp_pre[l[pos]-1][j]+dp_suf[r[pos]+1][ask-j]);
}
cout<<ans<<'\n';
}
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
Read(); Do_dp(); Solve();
return 0;
}
浙公網(wǎng)安備 33010602011771號