【bailian4102 】宠物小精灵之收服

bailian4102
这是二维背包裸题吧
最后统计了一下最小的代价获得ans 那么M-代价就是我们花费的体积

/* if you can't see the repay Why not just work step by step rubbish is relaxed to ljq */ #include <cstdio> #include <cstring> #include <iostream> #include <queue> #include <cmath> #include <map> #include <stack> #include <set> #include <sstream> #include <vector> #include <stdlib.h> #include <algorithm> using namespace std; #define dbg(x) cout<<#x<<" = "<< (x)<< endl #define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl #define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) typedef pair<int,int> pll; typedef long long ll; const int inf = 0x3f3f3f3f; const int _inf = 0xc0c0c0c0; const ll INF = 0x3f3f3f3f3f3f3f3f; const ll _INF = 0xc0c0c0c0c0c0c0c0; const ll mod = (int)1e9+7; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;} ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);} void exgcd(ll a,ll b,ll &x,ll &y,ll &d){if(!b) {d = a;x = 1;y=0;}else{exgcd(b,a%b,y,x,d);y-=x*(a/b);}}//printf("%lld*a + %lld*b = %lldn", x, y, d); /*namespace sgt { #define mid ((l+r)>>1) #undef mid }*/ const int MAX_N = 105; int v[MAX_N],w[MAX_N],dp[1025][525]; int main() { //ios::sync_with_stdio(false); //freopen("a.txt","r",stdin); //freopen("b.txt","w",stdout); int N,M,n; scanf("%d%d%d",&N,&M,&n); for(int i = 1;i<=n;++i) scanf("%d%d",&v[i],&w[i]); for(int i = 1;i<=n;++i) { for(int j = N;j>=v[i];j--) { for(int k = M;k>=w[i];k--) { dp[j][k] = max(dp[j][k],dp[j-v[i]][k-w[i]]+1); } } } int maxx = dp[N][M],ans= inf; for(int i = 0;i<=N;++i) { for(int j = 0;j<=M;++j) { if(dp[i][j]==maxx) { ans = min(ans,j); } } } printf("%d %dn",maxx,M-ans); //fclose(stdin); //fclose(stdout); //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl; return 0; }

相关知识

Bailian4102 宠物小精灵之收服【模拟】
宠物小精灵之收服
4978:宠物小精灵之收服
T1292：宠物小精灵之收服
[Acwing1022]宠物小精灵之收服
4102:宠物小精灵之收服
宠物小精灵之收服（二维背包）
AcWing 1022. 宠物小精灵之收服
【openjudge】宠物小精灵之收服
1292：宠物小精灵之收服

网址: 【bailian4102 】宠物小精灵之收服 https://www.mcbbbk.com/newsview948737.html