HDU 2809 God of War
개인적으로는 정확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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.