当前位置: 代码迷 >> 综合 >> Matrix Problem(动态规划)
  详细解决方案

Matrix Problem(动态规划)

热度:58   发布时间:2023-10-14 00:37:52.0

原题链接

题意

nnn头怪物,一个人打怪物,他有HHH点生命,SSS点攻击

打每只怪物需要消耗hih_ihi?生命,sis_isi?攻击,获得wiw_iwi?金钱,

如果被消耗光了可以用生命抵攻击,但是生命一旦为000,就结束战斗了。

思路

二维费用背包模板题加一点小变形。

枚举前i只怪物,生命为j,攻击为k时的可获得最多的金钱。

加上生命换攻击的限制是: 当攻击不够减时,看生命值减去需要消耗的生命值再减剩下的不够减的攻击值是否大于0,大于0说明够减。

当攻击力够减:f[j][k]=max(f[j][k],f[j?h[i][k?s[i]]]+w[i])f[j][k] = max (f[j][k], f[j - h[i][k - s[i]]] + w[i])f[j][k]=max(f[j][k],f[j?h[i][k?s[i]]]+w[i])
不够减时:f[j][k]=max(f[j][k],f[j?h[i]+k?s[i]][0]+w[i])f[j][k] = max(f[j][k], f[j - h[i] + k - s[i]][0] + w[i])f[j][k]=max(f[j][k],f[j?h[i]+k?s[i]][0]+w[i])

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;const int N = 1050;
int w[N], h[N], s[N], f[N][N];signed main()
{
    int n, H, S; cin >> n >> H >> S;for (int i = 1; i <= n; i ++ ){
    cin >> h[i] >> s[i] >> w[i];}for (int i = 1; i <= n; i ++ ){
    for (int j = H; j > h[i]; j -- ){
    for (int k = S; k >= 0; k -- ){
    if (k - s[i] >= 0){
    f[j][k] = max(f[j][k], f[j - h[i]][k - s[i]] + w[i]);}else if (j - h[i] + k  - s[i] > 0){
    f[j][k] = max(f[j][k], f[j - h[i] + k - s[i]][0] + w[i]);}}}}cout << f[H][S] << endl;return 0;
}
  相关解决方案