宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。小智来到小精灵狩猎场,想收服野生小精灵,但这需要使用精灵球和可能伤害皮卡丘。小智的目标是尽可能多地收服小精灵,并确保皮卡丘剩余体力尽可能多。

输入格式

  • 第一行包含三个整数:N,M,K,分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
  • 接下来的K行,每一行代表一个野生小精灵,包括两个整数:收服该小精灵需要的精灵球的数量,以及收服过程中对皮卡丘造成的伤害。

输出格式

一行,包含两个整数:C,R,分别表示最多收服C个小精灵,以及收服C个小精灵时皮卡丘的剩余体力值最多为R。

数据范围

0 < N ≤ 1000, 0 < M ≤ 500, 0 ≤ K ≤ 100

输入样例1

10 100 5
7 10
2 40
2 50
1 20
4 20

输出样例1

3 30

输入样例2

10 100 5
8 110
12 10
20 10
5 200
1 110

输出样例2

0 100

题目分析

01背包 二分查找

代码实现

#include <iostream>
using namespace std;
const int N = 1e3 + 10;

int n, m, k, q, t, dp[N][N];
int binary_search(int l, int r, int tar) {
    while(l <= r) {
        int mid = ((r - l) >> 1) + l;
        if (dp[n][mid] == tar) r = mid - 1;
        else if (dp[n][mid] > tar) r = mid - 1;
        else l = mid + 1;
    }
    return l;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    while(k--) {
        cin >> q >> t;
        for (int i = n; i >= q; --i) {
            for (int j = m; j >= t; --j)
                dp[i][j] = max(dp[i][j], dp[i - q][j - t] + 1);
        }
    }
    int sec = m - binary_search(0, m, dp[n][m]);
    if (sec) cout << dp[n][m] << ' ' << sec;
    else cout << dp[n][m] - 1 << ' ' << m - binary_search(0, m, dp[n][m - sec - 1]);
    return 0;
} 
分类: DP

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status