AcWing 1022. 宠物小精灵之收服
原题链接
简单
作者:
cylove
,
2024-04-19 00:13:25
,
所有人可见
,
阅读 2
维护二维信息01背包
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>
const int N = 105 ;
int f[1005][505] ;
/*
f[i , j , k]
表示考虑前 i 个精灵,在 j 个精灵球, 皮卡丘体力值剩余 k 是最多收服精灵数量
*/
int v[N] , w[N] ;
int n , m , k ;
int main()
{
std::ios::sync_with_stdio(false) ;
std::cin.tie(nullptr) ;
std::cin >> n >> m >> k ;
for(int i = 1 ; i <= k ; ++ i)
std::cin >> v[i] >> w[i] ;
for(int x = 1 ; x <= k ; ++ x)
for(int y = n ; y >= v[x] ; -- y)
for(int z = 0 ; z <= m - w[x] ; ++ z)
f[y][z] = std::max(f[y][z] , f[y - v[x]][z + w[x]] + 1 ) ;
int C = 0 , R = 0;
for(int i = 1 ; i <= m ; ++ i)
{
if ( f[n][i] >= C )
{
C = f[n][i] ;
R = i ;
}
}
std::cout << C << ' ' << R << '\n' ;
return 0 ;
}