Skip to content

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

3
10 100
1 3
-2 1
6 –5

Sample Output 1

1666

Sample Input 2

3
10 60
-5 6
4 –1
-6 5

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;
}