2022新生赛 玩石头 题解

这题乍一看是个背包，但是它对背包物品的重量进行了限制，而且我们没有手段得知当前物品是否大于前面所有物品。研究发现，纪念品最大价值不会超过4000.因此我们可以用类似于01背包的做法，以纪念品价值作为重量，纪念品重量作为价值来dp.打表可以发现，在给定数据的范围下，石头塔最多为三十层，则时髦值之和最大为3000，然后我们发现石头塔的重量从上到下，一定是严格递增的，不妨设dp[j]代表时髦值为j的情况下的最小重量，然后将所有石头按重量从小到大排序，然后按照题目的要求DP即可。

#include <bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define fo(i,a,b) for(int i=(a);i<(b);++i)
#define PII pair<int,int>
using namespace std;
const int N=1e5+5;
const int INF=1e18;
const int V=3505;

int n;
PII a[N];
int f[V];

signed main(){
    cin>>n;
    rep(i,1,n) cin>>a[i].first>>a[i].second;
    sort(a+1,a+1+n);
    rep(i,0,V) f[i]=INF;
    f[0]=0;

    for(int i=1;i<=n;i++){
        int w=a[i].first,v=a[i].second;
        for(int j=V;j>=v;j--){
            if(f[j-v]==INF) continue;
            if(w>f[j-v]){
                f[j]=min(f[j],f[j-v]+w);
            }
        }
    }

    for(int j=V;j>=0;j--){
        if(f[j]<INF) {
            cout<<j;
            return 0;
        }
    }
}