用c++解决这个问题:描述 We assume that there is a turn-based RPG game. You control an undefeated hero. In each round of this game, you can choose one enemy to attack, and its HP will decrease by 1. However, at the same time, all living enemies will attack you, and your HP will decrease by the sum of their DPS. If one enemy's HP drops equal to or below zero, it will die after this round, and it cannot attack you in the following rounds. Although your hero is undefeated, you need to choose the best strategy to kill all the enemies with the minimum HP loss. 输入 There are mutiple test cases. The first line of each test case contains the number of enemies N (1<=N<=20). Then N lines follow, with each containing two integers DPSi and HPi, which are the DPS and HP for each enemy (1<=DPSi, HPi<=1000) respectively. The inputs terminate at the end of the file (EOF). 输出 Output one line for each test, indicating the minimum HP loss.
时间: 2024-02-14 22:04:39 浏览: 129
rpg c++一个小游戏
这是一个比较典型的动态规划问题,可以使用一个二维数组 dp[i][j] 表示前 i 个敌人,你的健康值为 j 时的最小健康值损失。状态转移方程如下:
dp[i][j] = min(dp[i-1][j-k*dps[i]] + k*dps_sum - j)
其中 dps_sum 表示前 i 个敌人的总 DPS,k 表示攻击敌人 i 的次数,j-k*dps[i] 表示攻击敌人 i k 次后你的健康值,k*dps_sum-j 表示攻击敌人 i k 次后你的健康值损失。
最终的答案即为 dp[N][hero_hp],其中 hero_hp 表示你的初始健康值。具体实现可以参考下面的 C++ 代码:
```c++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 20 + 5;
const int MAXHP = 1000 + 5;
int n, hero_hp;
int dps[MAXN], hp[MAXN];
int dps_sum[MAXN];
int dp[MAXN][MAXHP];
int main() {
while (cin >> n) {
memset(dps_sum, 0, sizeof(dps_sum));
for (int i = 1; i <= n; i++) {
cin >> dps[i] >> hp[i];
dps_sum[i] = dps_sum[i-1] + dps[i];
}
cin >> hero_hp;
memset(dp, INF, sizeof(dp));
dp[0][hero_hp] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= hero_hp; j++) {
for (int k = 0; k*dps[i] <= j && k <= hp[i]; k++) {
dp[i][j] = min(dp[i][j], dp[i-1][j-k*dps[i]] + k*dps_sum[i] - j);
}
}
}
cout << dp[n][hero_hp] << endl;
}
return 0;
}
```
阅读全文