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

题目描述

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

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];
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() {
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) {
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;
}
``````