混合宝石理论实战塔max路线的dp算法 阅读 351
回复 8
欢迎您,游客!登录 或者 注册
1 跳转到:

castor_v_pollux

4
主题
3
回帖


星数:1
精品:0
灌水:3
权限:0
最近:2019-08-14
IP:*.*.*.*

发表于 2019-07-01 21:56:16   最后编辑于 2019-07-01 22:03:32楼主
混合宝石理论实战塔是一个单层转换塔,其形式与 无尽轮回、朝圣0F、冥中手0F和(被撤的)狼人杀预赛塔 很像,都是连通度很高的每个怪物守一个宝石形式。但是这个塔比之前的塔都要复杂,因为除了攻击防御还有魔防、剑盾以及中间一列加点怪。在乱撞了若干次打不过之后,尝试使用dp打出了33血的max。在说具体算法之前,不得不说这个塔数据设计十分精妙,加点加一次、两次和三次防均能以很少的血量通过,而且路线均与思维定式不同。

这类问题用动规的大思路已经很明白了,就是将各个位置的宝石取走/未取走看做状态,然后每一次打怪取宝石看做状态之间的转移,每个状态的最优血量取决于能够到达它的状态中到达它时最优的那个。但由于这个塔过于复杂,需要做一些先验假设,从而减小动规的状态空间。
假设1:由于中间一列加点怪必打,因此拿全中间的宝石只需要打大蝙蝠、冥灵魔王、初级法师、初级巫师中的一个即可,由于大蝙蝠伤害明显低于其它三个,因此其它三个怪都不打。
在假设1的前提下,原图可以分出32个操作单位:



动规的话,时间复杂度是O(n*2^n),空间复杂度是O(2^n),32有点太大了,于是我又加了个假设2。
假设2:开局前两个怪打骷髅人和红蝙蝠,从减伤来看这是很显然的。事实上,这里可以假设更多开头必打的怪和顺序,但假设的越多,越可能剪掉max路线,而剪掉两个对于我的机器内存已经够用,因此不再做更多假设。

由于中间有加点怪,因此在同一个局面下,有可能有不同的攻防魔防值,对于每个状态(共2^30个),需要维护一个表,表里记录此处可能的能力值与最高血量的对应。使用C++中unordered_map(即hash表)实现,每个表初始大小是56字节,另外还需要维护一个表记录之前表中每个条目的前一个状态(用来最后追溯路径),这样总占用空间大约是2^30*(56+56)=112G,可以接受。

castor_v_pollux

4
主题
3
回帖


星数:1
精品:0
灌水:3
权限:0
最近:2019-08-14
IP:*.*.*.*

发表于 2019-07-01 21:58:59   最后编辑于 2019-07-01 22:01:542楼
为了节省计算时间,代码中将不同能力时打各个怪的血量损耗都事先算出来,以避免重复计算。

代码中使用位运算来压缩状态、能力和路径,状态为一个30位的二进制数,每一位0表示未操作,1表示已操作,能力为攻击<<16|防御<<8|魔防,路径为打怪编号<<24|前一状态的能力(攻击<<16|防御<<8|魔防)。
最终的C++代码如下,运行时间为90秒,占用内存112G。

#include<iostream>
#include<cstring>
#include<unordered_map>
using namespace std;
#define N 30
#define INF 0x3f3f3f3f
#define TARGET (1<<N)-1
struct {
string name;
int hp,atk,def,special;
int p,q,r,s;
int pre;
int fight(int atk,int def,int mdef) {
int atk_per_time=atk-this->def;
if(atk_per_time<=0) return INF;
if(special==1) atk_per_time=1;
int t=(hp-1)/atk_per_time;
int def_per_time=this->atk-def;
if(special==2) def_per_time*=2;
int ans=t*def_per_time-mdef;
if(ans<0) ans=0;
return ans;
}
} a[N]={
{"蓝骑士",1111,60,11,0,0,0,0,0,0},
{"紫蝙蝠",925,74,11,0,0,0,0,0,5},
{"骷髅巫师",1235,61,11,0,0,0,0,0,10},
{"骷髅法师",1005,69,14,0,0,0,0,0,20},
{"骷髅王",610,60,15,2,0,1,1,2000,40},
{"怪王",1046,64,15,0,0,0,0,0,80},
{"骷髅武士",639,60,13,2,0,0,1,1000,65568},
{"迷失勇者",1011,61,16,0,0,0,0,0,64},
{"魔神武士",1047,50,30,2,0,0,0,12120,128},
//以上9个怪加点 
{"石头人",150,36,29,1,1,0,0,0,0},
{"铁面人",300,36,29,1,1,0,0,0,0},
{"小蝙蝠",600,44,19,0,1,0,0,0,0},
//{"红蝙蝠",581,50,10,0,1,0,0,0,0},
//{"骷髅人",800,45,8,0,1,0,0,0,0},
{"骷髅队长",660,43,17,0,1,0,0,0,0},
{"尖角怪",500,100,38,0,10,0,0,0,0},
{"红头怪",614,47,15,0,0,1,0,0,0},
{"青头怪",696,51,12,0,0,1,0,0,0},
{"大蝙蝠",305,49,30,0,0,1,0,1000,0},
{"骷髅士兵",664,50,15,0,0,1,0,0,0},
{"冥队长",520,57,16,0,0,1,0,0,0},
{"兽人武士",2000,34,29,0,1,1,0,2000,0},
{"影子战士",3000,35,22,0,1,1,0,2000,0},
{"高级法师",500,53,31,0,1,1,0,2000,0},
{"高级巫师",1000,61,13,0,1,1,0,2000,0},
{"中级卫兵",916,75,12,0,1,1,0,2000,0},
{"双手剑士",45,2000,0,2,1,1,0,2000,0},
{"尖角怪",500,100,38,0,0,10,0,0,0},
{"兽人",100,70,34,0,0,0,1,0,0},
{"绿头怪",173,79,30,0,0,0,1,0,0},
{"初级卫兵",159,78,36,0,0,0,1,0,0},
{"高级卫兵",267,61,35,0,0,0,1,0,0}
};
int hp_cache[N][7][32][32];
unordered_map<int,int> dp[1<<N];
unordered_map<int,int> path[1<<N];
void init_cache() {
for(int i=0;i<N;i++)
for(int mdef=0;mdef<7;mdef++)
for(int atk=0;atk<32;atk++)
for(int def=0;def<32;def++)
hp_cache[i][mdef][atk][def]=a[i].fight(atk+30,def+25,mdef*25);
}
void update(int mask,int atk,int def,int mdef,int hp,int p) {
int t=dp[mask][atk<<16|def<<8|mdef];
if(hp>t) {
dp[mask][atk<<16|def<<8|mdef]=hp;
path[mask][atk<<16|def<<8|mdef]=p;
}
}
void print_path(int mask,int key) {
if(!mask) return;
int action=path[mask][key];
int old_key=action&0xffffff;
action=action>>24;
print_path(mask-(1<<action),old_key);
cout<<a[action].name<<endl;
printf("Status:hp %d,atk %d,def %d,mdef %d\n",dp[mask][key],key>>16,key>>8&0xff,key&0xff);
}
int main() {
init_cache();
dp[0][32<<16|25<<8|0]=4605;
for(int mask=0;mask<TARGET;mask++) {
if(mask<<10==0) cout<<(mask>>22)<<endl;
auto&map=dp[mask];
for(auto&p:map) {
            int tmp=p.first;
int hp=p.second;
int atk=tmp>>16;
int def=tmp>>8&0xff;
int mdef=tmp&0xff;
for(int i=0;i<N;i++) {
if(mask&1<<i) continue;
if(a[i].pre&&!(mask&a[i].pre)) continue;//进不来 
int new_hp=hp-hp_cache[i][mdef][atk-30][def-25];
if(new_hp<=0) continue;
if(i<9) {
update(mask|1<<i,atk+a[i].p+1,def+a[i].q,mdef+a[i].r,new_hp+a[i].s,i<<24|tmp);
update(mask|1<<i,atk+a[i].p,def+a[i].q+2,mdef+a[i].r,new_hp+a[i].s,i<<24|tmp);
} else {
update(mask|1<<i,atk+a[i].p,def+a[i].q,mdef+a[i].r,new_hp+a[i].s,i<<24|tmp);
}
}
}
}
int best=-INF,best_key;
for(auto&p:dp[TARGET]) {
int tmp=p.first;
int hp=p.second;
int atk=tmp>>16;
int def=tmp>>8&0xff;
int mdef=tmp&0xff;
int hp_need=(5000-1)/(atk-35)*(110-def)-mdef*25;
if(hp-hp_need>best) {
best=hp-hp_need;
best_key=tmp;
}
}
printf("Best:%d\n",best);
print_path(TARGET,best_key);
}

真魔

0
主题
2
回帖


星数:1
精品:0
灌水:2
权限:0
最近:2019-08-05
IP:*.*.*.*

发表于 2019-07-01 22:10:183楼
神仙castor

笑沐泽

0
主题
4
回帖


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

发表于 2019-07-01 22:20:434楼
无敌castor

AM19

1
主题
6
回帖


星数:1
精品:0
灌水:15
权限:0
最近:2019-08-17
IP:*.*.*.*

发表于 2019-07-01 23:56:435楼
我什么时候才能有castor 0.00000000000000000001%强?

太难了

5
主题
10
回帖


星数:1
精品:0
灌水:15
权限:0
最近:2019-08-10
IP:*.*.*.*

发表于 2019-07-02 20:22:046楼
我什么时候才能有castor 0.00000000000000000001%强?

五十八

0
主题
1
回帖


星数:1
精品:0
灌水:0
权限:0
最近:2019-07-04
IP:*.*.*.*

发表于 2019-07-03 16:14:327楼
问一下,文章中说这个塔的空间复杂度是2^30,不用考虑加点吗?
castor_v_pollux: 考虑的,所以不止2^30,但绝大多数状态都因为血不够中途被剪了,所以实际跑起来贼快
2019-07-03 23:37:58

老黄鸡

0
主题
4
回帖


星数:1
精品:0
灌水:4
权限:0
最近:2019-08-04
IP:*.*.*.*

发表于 2019-07-06 02:11:198楼
我什么时候才能有castor 0.00000000000000000001%强?

fegfass13

0
主题
4
回帖


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

发表于 2019-07-08 14:38:479楼
我什么时候才能有castor 0.00000000000000000001%强?
另外lz源代码我可以拿去用吗?
castor_v_pollux: 可以,但跑不动
2019-07-10 11:09:15


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

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

您要对  说: