镜像结界max路线的dp算法 阅读 304
回复 7
欢迎您,游客!登录 或者 注册
1 跳转到:

castor_v_pollux

5
主题
4
回帖


星数:1
精品:0
灌水:3
权限:0
最近:2020-02-15
IP:*.*.*.*

发表于 2020-02-05 15:02:40楼主
在每层内,状态为(已打的怪的组合2^12,留的宝石数0~8),每个状态维护从能力(攻/防/封/崩)到最高血量的映射;
每层各状态各能力下:
(1)尝试打boss,如果击败boss,枚举加点并转移到下一层
(2)如果有留下的宝石,吃宝石,枚举加点并转移
(3)打未打的怪(注意角上的怪需要不被挡住),枚举加点并转移

困难模式消耗内存4.6G,运行时间90秒。

castor_v_pollux

5
主题
4
回帖


星数:1
精品:0
灌水:3
权限:0
最近:2020-02-15
IP:*.*.*.*

发表于 2020-02-05 15:04:082楼
C++代码:

#include<iostream>
#include<cstring>
#include<vector>
#include<unordered_map>
using namespace std;

#define dict unordered_map
#define ll long long

#define cc(atk, def, b1, b2) ((ll)(atk) << 50 | (ll)(def) << 40 | (ll)((b1) + 524288) << 20 | (ll)((b2) + 524288))
#define cc_atk(x) ((x) >> 50)
#define cc_def(x) ((x) >> 40 & 0x3ff)
#define cc_b1(x) (((x) >> 20 & 0xfffff) - 524288)
#define cc_b2(x) (((x) & 0xfffff) - 524288)
#define dd(hp, pre, times, ways, choices) ((ll)(times) << 35 | (ll)(ways) << 34 | (ll)(choices) << 32 | (ll)(pre) << 16 | (hp))
#define dd_hp(x) ((x) & 0xffff)
#define dd_pre(x) ((x) >> 16 & 0xffff)
#define dd_times(x) ((x) >> 35 & 0xf)
#define dd_ways(x) ((x) >> 34 & 0x1)
#define dd_choices(x) ((x) >> 32 & 0x3)

#define INF 0x3f3f3f3f
#define N 12
#define M 6
#define F 7

struct Monster {
string name;
int hp, atk, def;
int fight(int atk, int def) {
int atk_per_time = atk - this->def;
if(atk_per_time <= 0) return -1;
int def_per_time = this->atk - def;
if(def_per_time < 0) def_per_time = 0;
return (hp - 1) / atk_per_time * def_per_time;
}
} mons[M + 1] = {
{"中级卫兵"},
{"战士"},
{"双手剑士"},
{"灵骷髅"},
{"初级巫师"},
{"白衣武士"},
{"黑暗大法师"}
};

int mons_had[F][M + 1][3] = {
380, 34, 8,
370, 38, 7,
350, 52, 1,
450, 40, 5,
330, 46, 9,
430, 36, 13,
550, 46, 12,

380, 37, 13,
370, 42, 11,
350, 60, 3,
450, 46, 7,
330, 50, 15,
430, 39, 18,
550, 48, 15,

380, 43, 18,
370, 49, 15,
350, 67, 6,
450, 53, 12,
330, 57, 20,
430, 45, 24,
550, 55, 20,

480, 50, 20,
470, 55, 16,
450, 83, 7,
550, 61, 13,
430, 58, 22,
530, 48, 26,
550, 60, 24,

780, 42, 22,
770, 45, 20,
700, 98, 8,
850, 70, 14,
730, 60, 24,
830, 50, 30,
1000, 60, 25,

510, 65, 29,
500, 77, 22,
400, 117, 7,
580, 83, 13,
460, 80, 24,
560, 69, 30,
550, 77, 27,

410, 76, 34,
400, 85, 28,
380, 127, 9,
480, 89, 21,
360, 82, 31,
460, 73, 39,
864, 88, 38
};

struct Action {
int mon, pre, hp, diamond;
} actions[N] = {
{0, 1 << 1 | 1 << 4, 500, 1},
{2, 0, 500, 0},
{4, 0, 0, 1},
{5, 1 << 2 | 1 << 5, 500, 1},
{5, 0, 0, 1},
{1, 0, 500, 0},
{4, 0, 500, 0},
{3, 0, 0, 1},
{3, 1 << 6 | 1 << 9, 500, 1},
{1, 0, 0, 1},
{0, 0, 500, 0},
{2, 1 << 7 | 1 << 10, 500, 1}
};

//djd[times 0~1][ways 0~1][choices 0~3][changes 0~3]
vector<vector<vector<vector<int>>>> djd;

void init() {
int a[4] = {1, 1, -40, -65};
djd.resize(3);
//no jiadian
djd[0].resize(1);
djd[0][0].push_back(vector<int>(4, 0));
//one jiadian
djd[1].resize(2);
for(int way = 0; way < 2; ++way) {
int k = way * 2 - 1;
for(int choice = 0; choice < 4; ++choice) {
djd[1][way].push_back(vector<int>(4, 0));
djd[1][way][choice][choice] = a[choice] * k;
}
}
}

//state->((atk:10/def:10/b1:20/b2:20)->((times:2/ways:1/choices:2/pre:16/hp:16)))
dict<int, dict<ll, ll>> f[F + 1];

void dp() {
printf("Running dp...\n");
f[0][0][cc(20, 20, 450, 650)] = 2000;
for(int floor = 0; floor < F; ++floor) {
printf("\nFloor %d: (Initial states: %ld)\n", floor, f[floor][0].size());
//change monster's data
for(int i = 0; i <= M; ++i) {
mons[i].hp = mons_had[floor][i][0];
mons[i].atk = mons_had[floor][i][1];
mons[i].def = mons_had[floor][i][2];
}
//running common dp
for(int mask = 0; mask < (1 << N) - 1; ++mask) {
printf("\rmask=%x", mask);
for(int diamond = 8; diamond >= 0; --diamond) {
int mmask = diamond << N | mask;
if(f[floor].find(mmask) == f[floor].end()) continue;
for(auto &p : f[floor][mmask]) {
int atk = cc_atk(p.first);
int def = cc_def(p.first);
int b1 = cc_b1(p.first);
int b2 = cc_b2(p.first);
int hp = dd_hp(p.second);
//try to beat the boss
{
int damage = mons[M].fight(atk, def);
if(damage != -1 && damage < hp) {
int new_hp = hp - damage;
int time = 1, way = -1;
if(damage <= b1) way = 0;
else if(damage >= b2) way = 1;
if(way == -1) {
time = 0;
way = 0;
}
int l = djd[time][way].size();
for(int i = 0; i < l; ++i) {
auto &choice = djd[time][way][i];
ll key = cc(atk + choice[0], def + choice[1], b1 + choice[2], b2 + choice[3]);
int hhh = dd_hp(f[floor + 1][0][key]);
if(new_hp > hhh)
f[floor + 1][0][key] = dd(new_hp, mmask, time, way, i);
}
}
}
//transit inside floor
if(diamond > 0) {
int l = djd[1][1].size();
int new_mask = (diamond - 1) << N | mask;
for(int i = 0; i < l; ++i) {
auto &choice = djd[1][1][i];
ll key = cc(atk + choice[0], def + choice[1], b1 + choice[2], b2 + choice[3]);
int hhh = dd_hp(f[floor][new_mask][key]);
if(hp > hhh)
f[floor][new_mask][key] = dd(hp, N, 1, 1, i);
}
}
for(int k = 0; k < N; ++k) {
if(mask >> k & 1) continue;
if(actions[k].pre && !(mask & actions[k].pre)) continue;
int damage = mons[actions[k].mon].fight(atk, def);
if(damage != -1 && damage < hp) {
int new_hp = hp - damage;
int time = 1, way = -1;
if(damage <= b1) way = 0;
else if(damage >= b2) way = 1;
if(way == -1) {
time = 0;
way = 0;
}
new_hp += actions[k].hp;
int l = djd[time][way].size();
int new_mask = mask | 1 << k | (actions[k].diamond + diamond) << N;
for(int i = 0; i < l; ++i) {
auto &choice = djd[time][way][i];
ll key = cc(atk + choice[0], def + choice[1], b1 + choice[2], b2 + choice[3]);
int hhh = dd_hp(f[floor][new_mask][key]);
if(new_hp > hhh)
f[floor][new_mask][key] = dd(new_hp, k, time, way, i);
}
}
}
}
}
}
}
printf("\ndp finished!\n");
}

void print_path(int floor, int mmask, ll key) {
if(floor == 0 && mmask == 0) return;
ll tmp = f[floor][mmask][key];
int atk = cc_atk(key);
int def = cc_def(key);
int b1 = cc_b1(key);
int b2 = cc_b2(key);
int hp = dd_hp(tmp);
int pre = dd_pre(tmp);
int times = dd_times(tmp);
int ways = dd_ways(tmp);
int choices = dd_choices(tmp);
int old_atk = atk - djd[times][ways][choices][0];
int old_def = def - djd[times][ways][choices][1];
int old_b1 = b1 - djd[times][ways][choices][2];
int old_b2 = b2 - djd[times][ways][choices][3];
if(mmask == 0) {
//downstairs
print_path(floor - 1, pre, cc(old_atk, old_def, old_b1, old_b2));
printf("boss\t加点%d\tatk=%d, def=%d, b1=%d, b2=%d, hp=%d\n",
choices, atk, def, b1, b2, hp);
} else {
int mask = mmask & ((1 << N) - 1);
int diamond = mmask >> N;
int old_mask;
if(pre == N)
old_mask = (diamond + 1) << N | mask;
else if(actions[pre].diamond)
old_mask = (diamond - 1) << N | (mask - (1 << pre));
else
old_mask = mmask - (1 << pre);
print_path(floor, old_mask, cc(old_atk, old_def, old_b1, old_b2));
printf("%d\t加点%d\tatk=%d, def=%d, b1=%d, b2=%d, hp=%d\n",
pre, times == 1 ? choices : -1, atk, def, b1, b2, hp);
}
}

void find_best() {
int best_hp = 0;
ll best_key;
for(auto &p : f[F][0]) {
int hp = dd_hp(p.second);
if(hp > best_hp) {
best_hp = hp;
best_key = p.first;
}
}
if(best_hp == 0) {
printf("No solution!\n");
return;
}
print_path(F, 0, best_key);
}

int main() {
init();
dp();
find_best();
}

bdf

2
主题
2
回帖


星数:1
精品:0
灌水:0
权限:0
最近:2020-02-16
IP:*.*.*.*

发表于 2020-02-05 17:51:513楼
好。。。。。。强

老黄鸡

0
主题
12
回帖


星数:1
精品:0
灌水:4
权限:0
最近:2020-02-17
IP:*.*.*.*

发表于 2020-02-06 14:08:174楼
我们甚至能在魔塔里学算法

hppally

0
主题
6
回帖


星数:1
精品:0
灌水:1
权限:0
最近:2020-02-10
IP:*.*.*.*

发表于 2020-02-06 14:26:075楼

我能听见风的声音

0
主题
1
回帖


星数:1
精品:0
灌水:0
权限:0
最近:2020-02-13
IP:*.*.*.*

发表于 2020-02-06 14:28:066楼
!!!

Teenager

0
主题
1
回帖


星数:1
精品:0
灌水:0
权限:0
最近:2020-02-08
IP:*.*.*.*

发表于 2020-02-08 13:31:247楼
太强了

nnnn123456789

0
主题
2
回帖


星数:1
精品:0
灌水:0
权限:0
最近:2020-02-19
IP:*.*.*.*

发表于 2020-02-11 21:43:488楼
我用VS2019跑了一下, 耗内存8.2G[= =]
castor_v_pollux: MSVC的库和linux的库有差别
2020-02-12 16:11:21
nnnn123456789: 回复 @castor_v_pollux: %
2020-02-13 17:48:27


1 跳转到:
您需要 登录 后回复此贴;没有账号? 现在注册 
为此附件填写阅读权限与下载售价:

阅读权限:  积分不少于此数值才能浏览附件
下载售价:  每位下载者需向您支付的积分数

您要对  说: