狼人杀预赛(已作废)max路线的dp算法 阅读 339
回复 2
欢迎您,游客!登录 或者 注册
1 跳转到:

castor_v_pollux

4
主题
3
回帖


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

发表于 2019-06-28 23:52:39   最后编辑于 2019-06-28 23:52:56楼主
游戏链接https://h5mota.com/games/lrs1y2/
算法太水了,直接贴代码吧,复杂度24*2^24,我的破机器7秒出结果


#include<iostream>
#include<cstring>
using namespace std;
struct {
string name;
int hp,atk,def,jwl;
int fight(int atk,int def) {
return (hp-1)/(atk-this->def)*(this->atk-def);
}
} mons[24]={
{"初级莱姆",628,58,30,0},
{"红史莱姆",584,62,29,1},
{"青头怪",553,64,29,1},
{"怪王",678,55,29,0},
{"小蝙蝠",602,60,30,0},
{"大蝙蝠",603,61,30,1},
{"红蝙蝠",649,57,30,0},
{"冥灵魔王",607,59,30,0},
{"骷髅人",565,63,30,1},
{"骷髅士兵",524,65,30,1},
{"骷髅队长",651,56,30,0},
{"冥队长",501,66,30,1},
{"兽人",651,55,30,0},
{"兽人武士",638,56,29,0},
{"中级卫兵",501,64,30,1},
{"影子战士",611,58,29,0},
{"高级巫师",541,62,30,1},
{"高级法师",579,60,29,0},
{"初级巫师",563,61,29,1},
{"初级法师",594,59,29,0},
{"初级卫兵",522,63,29,1},
{"石头人",626,57,29,0},
{"高级卫兵",479,65,29,1},
{"双手剑士",458,66,29,1}
};
#define TARGET ((1<<24)-1)
int dp[1<<24]={15000};
int path[1<<24];
int f(int mask,int atk,int def) {
if(dp[mask]) return dp[mask];
int m=0,n;
for(int i=0;i<24;i++) {
int x=1<<i;
if(mask&x) {
int old_atk=atk-mons[i].jwl;
int old_def=def+mons[i].jwl-1;
int t=f(mask-x,old_atk,old_def)-mons[i].fight(old_atk,old_def);
if(t>m) {
m=t;
n=i;
}
}
}
path[mask]=n;
return dp[mask]=m;
}
void print_path(int mask) {
if(!mask) return;
int action=path[mask];
print_path(mask-(1<<action));
cout<<mons[action].name<<' ';
}
int main() {
printf("Max:%d\n",f(TARGET,63,49)-6665);
print_path(TARGET);
}

葫芦娃救爷爷

0
主题
1
回帖


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

发表于 2019-06-30 20:31:452楼
动归的思路大致懂,中间算的那个递归函数,虽然我大致懂是从递归函数的最内一层倒算到最外一层,但还是很难想象其过程是怎样的。。
如果使用两个for循环,例如:
for(i=0;i<2^24;i++)
    for(j=0;j<24;j++)
这样就很好理解啦
castor_v_pollux: 是的,你的写法也正确。动规有两种写法,一种是自底向上,先算部分,再算整体,使用循环的方式,这是你的写法;另一种是自顶向下,先算整体,算整体的时候如果部分还没有被算,再停下来去算部分,使用递归的方式,这种动规也叫记忆化搜索,这是我的写法。 这两种写法的区别在于:循环好写,也易于理解...
2019-07-01 10:33:53
castor_v_pollux: 回复 @castor_v_pollux: 被吞了一大半/无感 算了算了,总之这题写循环更好,但有的题只能写递归
2019-07-01 10:46:29

没有

8
主题
9
回帖


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

发表于 2019-07-02 01:11:303楼

说实话刚看见那个塔让我想起了这个

https://h5mota.com/games/random/



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

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

您要对  说: