11124: 【原1124】我把助教团的平均智商拉低了

题目描述

author: Zhipeng Chen 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1124

Description

我在PPCA期间刻苦学习，孜孜不倦，经常精疲力竭，于是需要一些活动来恢复身心，需恢复的数值主要有两项：体力、智力。每项活动都会对这两项数值造成一定影响，例如，玩游戏会降低10点体力，增加1点智力；与妹子共进晚餐会增加4点体力和3点智力；如果跑圈的话，会降低3点体力和1点智力，诸如此类。但是，同一项活动不能重复进行，例如与妹子连吃2顿晚餐（甚至更多）会被讨厌的。。。

现在我需要休息一会儿，有n项活动可以参加，我希望在不计时间的情况下，按顺序参加完若干项活动后，所得到的体力值与智力值的积尽可能大。另外，现在，我是有一定体力值和智力值的，在整个过程中，需要保持体力值大于等于0；在参加完所选活动后，体力值必须大于0，否则会死人的，智力值必须大于70，否则会弱智的，若无法达到上述要求，那还不如死了算了，就输出“Death”好了。

Input Format

共n+2行。

第一行：活动项数n 对于30%数据：n<=50 对于100%数据：n<=400

第二行：我的初始体力值、智力值，在0-1000之间

第3至n+2行：每行两个数，表示第i项活动对体力的影响xi、对智力的影响yi xi、yi绝对值均小于1000，其绝对值之和均小于30000

Output Format

一行：在体力值大于0，智力值大于70的情况下的最大体力值*智力值；若无法满足体力值大于0且智力值大于70，则输出：Death。

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Death

Limits

30% n<=50, 100% n<=400

FineArtz's solution

/* 我把助教团的平均智商拉低了 */
#include <iostream>
using namespace std;

const int INF = 2000000;
const int MAXH = 33000;

int n;
int hp, iq;
int a[405], b[405];
int f[405][MAXH + 5] = {0};

int main(){
    cin >> n;
    cin >> hp >> iq;
    for (int i = 1; i <= n; ++i)
        cin >> a[i] >> b[i];
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= MAXH; ++j)
            f[i][j] = -INF;
    f[0][hp] = iq;
    for (int i = 1; i <= n; ++i){
        for (int j = 0; j <= MAXH - 1000; ++j){
            if (j >= a[i] && f[i - 1][j - a[i]] != -INF && f[i - 1][j - a[i]] + b[i] > f[i - 1][j]){
                f[i][j] = f[i - 1][j - a[i]] + b[i];
            }
            else
                f[i][j] = f[i - 1][j];
        }
    }
    int ans = -INF;
    for (int i = 1; i <= MAXH; ++i){
        if (f[n][i] > 70 && f[n][i] * i > ans)
            ans = f[n][i] * i;
    }
    if (ans == -INF)
        cout << "Death" << endl;
    else
        cout << ans << endl;
    return 0;
}

WashSwang's solution

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[410][33000],x[500],y[500],sx,sy,n,ans;
int main() {
    cin>>n>>sx>>sy;
    for (int i=1;i<=n;++i)
        cin>>x[i]>>y[i];
    memset(dp,-40000,sizeof(dp));
    dp[0][sx]=sy;
    for (int i=1;i<=n;++i)
        for (int j = 0; j < 32000; ++j) {
            dp[i][j] = dp[i - 1][j];
            if ((j >= x[i]) && (dp[i - 1][j - x[i]] > -40000) && (dp[i - 1][j - x[i]] + y[i] > dp[i][j]))
                dp[i][j] = dp[i - 1][j - x[i]] + y[i];
        }
    for (int i=1;i<32000;++i)
        if ((dp[n][i]>70)&&(i*dp[n][i]>ans))
            ans=i*dp[n][i];
    if (ans!=0) cout<<ans<<endl;
    else cout<<"Death"<<endl;
    return 0;
}

yyong119's solution

#include <cstdio>
#include <algorithm>
#define MAX_H 35000
using namespace std;
int n, init_H, init_I;
int f[MAX_H];
inline int read() {
    char ch = getchar(); int flag = 1, res = 0;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
    return res * flag;
}
int main() {
    n = read(); init_H = read(); init_I = read();
    for (register int i = 0; i < MAX_H; ++i)
        f[i] = -MAX_H;//智力中间可负，需要初始化为负数，不然会卡第2个测试点
    f[init_H] = init_I;
    for (register int i = 0; i < n; ++i) {
        int health = read(), intell = read();
        if (health < 0 && intell < 0) continue;
        if (health > 0) {
            for (register int j = MAX_H - 1; j >= health; --j)
                if (f[j - health] > -MAX_H)
                    f[j] = max(f[j], f[j - health] + intell);
        }
        else {
            for (register int j = 0; j < MAX_H + health; ++j)
                if (f[j - health] > -MAX_H)
                    f[j] = max(f[j], f[j - health] + intell);
        }
    }
    int ans = 0;
    for (register int i = 1; i < MAX_H; ++i)
        if (f[i] > 70) ans = max(ans, i * f[i]);
    if (ans)
        printf("%d\n", ans);
    else
        printf("Death");
    return 0;
}