HDU 2809 God of War

6156 단어
상압 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; }

좋은 웹페이지 즐겨찾기