Poker小塔的DP代码 阅读 200
回复 1
欢迎您,游客!登录 或者 注册
1 跳转到:

castor_v_pollux

7
主题
5
回帖


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

发表于 2020-08-24 14:59:41楼主
运行时间20秒,占用内存141M。

castor_v_pollux

7
主题
5
回帖


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

发表于 2020-08-24 15:00:492楼
//[partial]
//node: (atk, def, mdef) making each monster score > some threhold
//mons mask: 2^25
//money->hp

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

#define ll long long
#define dict unordered_map
#define N 25
#define ATK_MAX 90
#define DEF_MAX 100
#define MDEF_MAX 130
#define cc(atk, def, mdef) ((atk) << 20 | (def) << 10 | (mdef))
#define dd(atk, def, mdef, mon, money, hp) ((ll)(atk) << 54 | (ll)(def) << 47 | (ll)(mdef) << 39 | (ll)(mon) << 34 | (ll)(money) << 24 | (hp))

enum Special {
NONE, XIANGONG, MOGONG, JIANGU, SANLIANJI
};

struct Monster {
int hp, atk, def;
Special special;
int fight(int atk, int def, int mdef) {
int atk_per_time = atk - this->def;
if(atk_per_time <= 0) return -1;
if(special == JIANGU) atk_per_time = 1;
int times = (hp - 1) / atk_per_time;
if(special == XIANGONG) ++times;
else if(special == SANLIANJI) times *= 3;
int damage_per_time = special == MOGONG ? this->atk : this->atk - def;
if(damage_per_time < 0) damage_per_time = 0;
int damage = damage_per_time * times - mdef;
return damage < 0 ? 0 : damage;
}
} monsInfo[] = {
{480, 32, 8},
{360, 40, 12},
{270, 55, 1, XIANGONG},
{880, 35, 15},
{550, 80, 0},
{1200, 28, 10, MOGONG},
{600, 89, 5},
{640, 48, 16},
{800, 103, 15},
{1475, 40, 25},
{750, 75, 20},
{850, 100, 25},
{100, 60, 0, JIANGU},
{1444, 39, 20, MOGONG},
{500, 80, 30},
{5000, 56, 28},
{1400, 81, 39},
{2000, 95, 35},
{200, 150, 30, SANLIANJI},
{850, 141, 48},
{1800, 90, 40},
{1250, 40, 40, MOGONG},
{3000, 110, 55},
{1280, 63, 45, MOGONG},
{300, 200, 60}
};

int rule[10000];
// mon -> groups of adm
vector<vector<int>> mons[N];
// internal constraint: each adm must be potential to clear all monsters
dict<int, int> cons;
// atk/def/mdef -> (mons_mask -> (money -> hp|path))
//path = (atk:7|def:7|mdef:8|mon:5|money:10|hp:24)
dict<int, dict<int, dict<int, ll>>> f;

void initRule() {
for(int i = 1; i < 10000; ++i) {
vector<int> digit;
for(int j = i; j; j /= 10) if(j % 10) digit.push_back(j % 10);
for(int j = 11; digit.size() < 4; j += 2) digit.push_back(j);
sort(digit.begin(), digit.end());
int score = 0;
bool e1, e2, e3, f1, f2, f3;
e1 = digit[0] == digit[1];
e2 = digit[1] == digit[2];
e3 = digit[2] == digit[3];
f1 = digit[1] - digit[0] == 1;
f2 = digit[2] - digit[1] == 1;
f3 = digit[3] - digit[2] == 1;
if(e1 || e2 || e3) score += 2;
if(f1 && f2 || f2 && f3) score += 5;
if(e1 && e2 || e2 && e3) score += 9;
if(e1 && e3) score += 12;
if(f1 && f2 && f3) score += 18;
if(e1 && e2 && e3) score += 30;
rule[i] = score;
}
}

void initMons() {
int cnt = 0, state = 0;
for(int mon = 0; mon < N; ++mon) {
int t = monsInfo[mon].fight(20, 20, 0);
// Customize this threhold to adjust accuracy
int threhold = t == -1 ? 53 : t < 1000 ? 5 : 53;
if(monsInfo[mon].special == MOGONG)
for(int atk = 20; atk <= ATK_MAX; ++atk)
for(int mdef = 0; mdef <= MDEF_MAX; ++mdef) {
int damage = monsInfo[mon].fight(atk, 0, mdef);
if(damage < 0) continue;
if(rule[damage % 10000] >= threhold) {
mons[mon].push_back(vector<int>());
for(int def = 20; def <= DEF_MAX; ++def)
mons[mon].back().push_back(cc(atk, def, mdef));
}
}
else if(monsInfo[mon].special == JIANGU)
for(int def = 20; def <= DEF_MAX; ++def)
for(int mdef = 0; mdef <= MDEF_MAX; ++mdef) {
int damage = monsInfo[mon].fight(1, def, mdef);
if(damage < 0) continue;
if(rule[damage % 10000] >= threhold) {
mons[mon].push_back(vector<int>());
for(int atk = 20; atk <= ATK_MAX; ++atk)
mons[mon].back().push_back(cc(atk, def, mdef));
}
}
else
for(int atk = 20; atk <= ATK_MAX; ++atk)
for(int def = 20; def <= DEF_MAX; ++def)
for(int mdef = 0; mdef <= MDEF_MAX; ++mdef) {
int damage = monsInfo[mon].fight(atk, def, mdef);
if(damage < 0) continue;
if(rule[damage % 10000] >= threhold) {
mons[mon].push_back(vector<int>());
mons[mon].back().push_back(cc(atk, def, mdef));
}
}
int k = 0;
for(auto &v : mons[mon]) k += v.size();
printf("Mon %d: %d %d\n", mon, mons[mon].size(), k);
state += mons[mon].size();
cnt += k;
}
printf("%d %d\n", state, cnt);
}

void initConstraint() {
for(int mon = 0; mon < N; ++mon)
for(auto &v : mons[mon])
for(int adm : v)
cons[adm] = 0;
for(int mon = 0; mon < N; ++mon)
for(auto &v : mons[mon])
for(int adm : v) {
int atk = adm >> 20;
int def = adm >> 10 & 0x3ff;
int mdef = adm & 0x3ff;
for(auto &p : cons) {
int cadm = p.first;
int catk = cadm >> 20;
int cdef = cadm >> 10 & 0x3ff;
int cmdef = cadm & 0x3ff;
if(catk <= atk && cdef <= def && cmdef <= mdef)
cons[cadm] |= 1 << mon;
}
}
}

void init() {
initRule();
initMons();
initConstraint();
}

int best_hp, best_adm, best_money;

void win(int hp, int atk, int def, int mdef, int money) {
int cost = 0;
if(atk < 81) cost += (81 - atk) * 7;
if(def < 100) cost += (100 - def) * 4;
if(cost > money) return;
hp = hp + (money - cost) * 150 - 15300;
if(hp > best_hp) {
best_hp = hp;
best_adm = cc(atk, def, mdef);
best_money = money;
}
}

void print_path(int adm, int mask, int money) {
if(mask == 0) return;
ll t = f[adm][mask][money];
int atk = t >> 54;
int def = t >> 47 & 0x7f;
int mdef = t >> 39 & 0xff;
int mon = t >> 34 & 0x1f;
int oldmoney = t >> 24 & 0x3ff;
int hp = t & 0xffffff;
print_path(cc(atk, def, mdef), mask - (1 << mon), oldmoney);
atk = adm >> 20;
def = adm >> 10 & 0x3ff;
mdef = adm & 0x3ff;
printf("Action %d, atk=%d, def=%d, mdef=%d, money=%d, hp=%d\n", mon, atk, def, mdef, money, hp);
}

void dp() {
int progress = 0;
f[cc(20, 20, 0)][0][10] = 15000; // 60 -> 10 for Easy
for(int catk = 20; catk <= ATK_MAX; ++catk)
for(int cdef = 20; cdef <= DEF_MAX; ++cdef)
for(int cmdef = 0; cmdef <= MDEF_MAX; ++cmdef)
if(f.find(cc(catk, cdef, cmdef)) != f.end()) {
auto &ff = f[cc(catk, cdef, cmdef)];
vector<int> masklist;
for(auto &p : ff) masklist.push_back(p.first);
sort(masklist.begin(), masklist.end());
for(int mask : masklist)
for(int mon = 0; mon < N; ++mon) {
if(mask >> mon & 1) continue;
for(auto &group : mons[mon])
for(int adm : group) {
// Next adm platform
int atk = adm >> 20;
int def = adm >> 10 & 0x3ff;
int mdef = adm & 0x3ff;
if(atk < catk || def < cdef || mdef < cmdef) continue;
int newmask = mask | 1 << mon;
if((newmask | cons[adm]) != (1 << N) - 1) continue;
int cost = (atk - catk) * 7 + (def - cdef) * 4 + (mdef - cmdef);
for(auto &p : ff[mask]) {
int money = p.first;
if(cost > money) continue;
int damage = monsInfo[mon].fight(atk, def, mdef);
int score = rule[damage % 10000];
int hp = p.second & 0xffffff;
int hpcost = hp <= damage ? (damage - hp) / 150 + 1 : 0;
int moneyLeft = money - cost - hpcost;
if(moneyLeft < 0) continue;
int newmoney = moneyLeft + score;
int newhp = hpcost * 150 + hp - damage;
if(newhp > (f[cc(atk, def, mdef)][newmask][newmoney] & 0xffffff)) {
f[cc(atk, def, mdef)][newmask][newmoney] = dd(catk, cdef, cmdef, mon, money, newhp);
if(newmask == (1 << N) - 1) win(newhp, atk, def, mdef, newmoney);
}
}
break; // Only use the first in each group
}
}
printf("Progress: %d, atk: %d, def: %d, mdef: %d, Best: %d\n", progress++, catk, cdef, cmdef, best_hp);
}
printf("Best hp: %d\n", best_hp);
print_path(best_adm, (1 << N) - 1, best_money);
}

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


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

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

您要对  说: