POJ 4978:宠物小精灵之收服

“ Ctrl AC！一起 AC！”

题目：http://noi.openjudge.cn/ch0206/4978/

思路：

二维01背包，抓的话球和体力同时减掉，否则都不减

代码：

#include <iostream>

#include <algorithm>

int num[101];

int wei[101];

int dp[1001][501];

using namespace std;

int main()

{

int n, m, k;

cin >> n >> m >> k;

for (int i = 1; i <= k; i++) {

cin >> num[i] >> wei[i];

}

for (int i = 1; i <= k; i++) {

for (int j = n; j >= 0; j--) {

for (int x = m; x >= 0; x--) {

if (j - num[i] >= 0 && x - wei[i] >= 0)

dp[j][x] = max(dp[j][x], dp[j - num[i]][x - wei[i]] + 1);

}

}

}

cout << dp[n][m] << " ";

for (int i = 0; i <= m; i++) {

if (dp[n][i] == dp[n][m]) {

cout << m - i << endl;

break;

}

}

return 0;

}

“ Ctrl AC！一起 AC！”