HDU 2809 God of War

状压DP。我认为是数据水了，用打死了哪几只作为状态，AC代码只需要保存当前状态的最大血量，完全没有考虑攻击力大小。

个人认为正确DP应该这样的：dp[状态][等级]，但这样写不能AC，时间复杂度会很大，但答案应该是正确的。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;

struct X
{
    int HP;
    int ATI;
    int DEF;
    int e;
    int lv;
} dp[(1 << 20) + 10], A[25];

int In_ATI, In_DEF, In_HP;
int ATI, DEF, HP;
int n;
int base[25];

int MAX(int a, int b)
{
    if (a>b) return a;
    return b;
}

void read()
{
    scanf("%d", &n);
    for (int i = 0; i<n; i++)
    {
        string name;
        cin >> name;
        scanf("%d%d%d%d", &A[i].ATI, &A[i].DEF, &A[i].HP, &A[i].e);
    }
}

void init()
{
    dp[0].ATI = ATI, dp[0].DEF = DEF, dp[0].HP = HP;
    dp[0].e = 0, dp[0].lv = 1;

    for (int i = 1; i<(1 << n); i++) dp[i].HP = -1;
}

int f(int num1, int num2)
{
    int A1 = MAX(1, dp[num1].ATI - A[num2].DEF);
    int A2 = MAX(1, A[num2].ATI - dp[num1].DEF);

    int HP1 = dp[num1].HP;
    int HP2 = A[num2].HP;

    int tot1, tot2;
    if (HP2%A1 == 0) tot1 = HP2 / A1;
    else tot1 = HP2 / A1 + 1;

    if (HP1%A2 == 0) tot2 = HP1 / A2;
    else tot2 = HP1 / A2 + 1;

    if (tot1 <= tot2) return HP1 - A2*(tot1 - 1); //返回吕布打完后的血量
    return -1; //返回吕布被打死
}

void work()
{
    for (int i = 1; i<(1 << n); i++)
    {
        int tot = 0, tmp = i;
        while (tmp) base[tot++] = tmp % 2, tmp = tmp / 2;

        for (int j = 0; j<tot; j++)
        {
            if (base[j])
            {
                int pre = i - (1 << j);
                if (dp[pre].HP == -1) continue;

                int lx = f(pre, j);
                if (lx == -1) continue;

                int hp = lx;
                int e = dp[pre].e + A[j].e;
                int lv = dp[pre].lv;
                int ati = dp[pre].ATI;
                int def = dp[pre].DEF;

                if (e >= 100 * dp[pre].lv)
                {
                    hp = hp + In_HP;
                    ati = ati + In_ATI;
                    def = def + In_DEF;
                    lv++;
                }

                if (hp>dp[i].HP)
                {
                    dp[i].e = e;
                    dp[i].lv = lv;
                    dp[i].HP = hp;
                    dp[i].ATI = ati;
                    dp[i].DEF = def;
                }
            }
        }
    }

    if (dp[(1 << n) - 1].HP == -1) printf("Poor LvBu,his period was gone.
");
    else printf("%d
", dp[(1 << n) - 1].HP);
}

int main()
{
    while (~scanf("%d%d%d%d%d%d", &ATI, &DEF, &HP, &In_ATI, &In_DEF, &In_HP))
    {
        read();
        init();
        work();
    }
    return 0;
}