鱼C论坛Python精英挑战赛（第二季05期）

yanchen1

def gen_skill(boss_skill):
    time=0
    player_skill=[]
    boss=100
    player=100
    cure=0
    while player>0 and len(boss_skill)!=time:
        if cure>0:
            player+=10
        if boss_skill[time]=='斩杀':
            if player>45 and boss<10:
                boss-=10
                player_skill.append('攻击')
                print('攻击')
                if boss <=0:
                    break;
            elif player>55 and boss<20:
                player-=10
                boss-=20
                player_skill.append('搏命一击')
                print('搏命一击')
                if boss <=0:
                    break;     
            else:
                player_skill.append('躲闪')
                print('躲闪')
        else:
            if boss_skill[time]=='普通攻击':
                player-=15
            if boss_skill[time]=='致命一击':
                player-=25
            if player>35 :
                player-=10
                boss-=20
                player_skill.append('搏命一击')
                print('搏命一击')
                if boss <=0:
                    break;
            elif player>10 and boss<20:
                player-=10
                boss-=20
                player_skill.append('搏命一击')
                print('搏命一击')
                if boss <=0:
                    break;
            elif boss<10 :
                boss-=10
                player_skill.append('攻击')
                print('攻击')
                if boss <=0:
                    break;
            elif player<=25 and cure==0:
                player+=30
                cure=3
                player_skill.append('治疗')
                print('治疗')
            else :
                boss-=10
                player_skill.append('攻击')
                print('攻击')
                if boss <=0:
                    break;
        if cure>0:
            cure-=1
        boss+=3
        if boss>100:
            boss=100
        time+=1
        print(player)
        print(boss)
    if boss>0:
        print('lose')
    print(time)
    return player_skill
boss_skill =   ['致命一击', '普通攻击', '致命一击', '斩杀', '致命一击', '斩杀', '普通攻击', '致命一击', '斩杀', '普通攻击', '致命一击', '普通攻击', '致命一击', '斩杀', '致命一击', '斩杀', '普通攻击', '致命一击', '斩杀', '普通攻击', '致命一击', '普通攻击', '致命一击', '斩杀', '致命一击', '斩杀', '普通攻击', '致命一击', '斩杀', '普通攻击']
player_skill=gen_skill(boss_skill)
print(player_skill)
#写的比较水，很多没想到的，希望大家能多提提意见，而且我最后一个示例30步没做出来

gunjang

采用暴力法，采用广度优先
剪枝很简单，取BossHP相同时，playerHP最高的那个（考虑Buff）
这样每次结果的待选最高只有100种，可以接受
得到的结果肯定是最优解。。。
五种答案分别回合数是9 10 20 13 20，其中1 2 5比贪心法都少了一个回合

1. def gen_skill(boss_skill):
   
2.         bossDamage = {'普通攻击':15,'致命一击':25,'斩杀':45}
   
3.         #A D E H
   
4.         psDict ={'A':'攻击','D':'搏命一击','E':'躲闪','H':'治疗'}
   
5.         currstate = [0 for x in range(101)] # index is BossHP
   
6.         currstate[100] = ['',100, 0] # playskill HP Buff
   
7.        
   
8.         for bs in boss_skill:
   
9.                 damage = bossDamage[bs]
   
10.                 nextstate = [0 for x in range(101)] # index is BossHP
    
11.                 for index in range(1, 101):
    
12.                         if currstate[index] == 0:
    
13.                                 continue
    
14. 
    
15.                         curr = currstate[index]
    
16.                         for pk in 'ADEH':
    
17.                                 pHP = curr[1]
    
18.                                 buff = curr[2]-1
    
19.                                 if buff > 0: pHP += 10
    
20.                                 pHP -= damage
    
21.                                 bHP = index+3
    
22.                                 if pk == 'A':
    
23.                                         bHP -= 10
    
24.                                 elif pk == 'D':
    
25.                                         bHP -= 20
    
26.                                         pHP -= 10
    
27.                                 elif pk == 'H':
    
28.                                         pHP += 30
    
29.                                         buff = 3
    
30.                                 if pHP > 100: pHP = 100
    
31.                                 if bHP > 100: bHP = 100
    
32.                                 #else: pass # ignore
    
33.                                 if pHP <= 0:
    
34.                                         continue
    
35.                                 ps = curr[0]+pk
    
36.                                 if bHP <= 0:
    
37.                                         return [psDict[x] for x in ps] #, '{0} round'.format(len(ps)), bHP, pHP
    
38.                                
    
39.                                 if (nextstate[bHP] == 0) or (nextstate[bHP][1] < pHP):
    
40.                                         nextstate[bHP] = [ps, pHP, buff]
    
41.                                 elif (nextstate[bHP][1]==pHP) and (buff>1) and (buff > curr[2]):
    
42.                                         nextstate[bHP] = [ps, pHP, buff]
    
43.                 currstate = nextstate                               
    
44. 
    
45. 
    
46.         return []
    

复制代码

jerryxjr1220

gunjang 发表于 2017-8-24 10:43
采用暴力法，采用广度优先
剪枝很简单，取BossHP相同时，playerHP最高的那个（考虑Buff）
这样每次结果的 ...

Boss Skill 3 最少可以19回合结束

贪心算法可以给出的最小回合数是9,10,19,13,20

gunjang

jerryxjr1220 发表于 2017-8-24 10:52
Boss Skill 3 最少可以19回合结束

贪心算法可以给出的最小回合数是9,10,19,13,20

好吧，可能有小bug没发现。。。

达不六

1. # -*- coding: utf-8 -*-
   
2. import time
   
3. star = time.clock()
   
4. 
   
5. def gen_skill(boss_skill):
   
6.    
   
7.     skill = {"普通攻击":15, "致命一击":25, "斩杀":45, "攻击":10, "搏命一击":20}
   
8.     nm_pg = boss_skill.count('普通攻击')
   
9.     nm_zm = boss_skill.count('致命一击')
   
10.     nm_zs = boss_skill.count('斩杀')
    
11.     hurt = (nm_pg*15+nm_zm*25+nm_zs*45)/30    # 技能列表中每个回合的平均伤害
    
12.     if 15 <= hurt <25 :                       # 对技能列表的难度分为两级
    
13.         e = 4
    
14.     elif 25 <= hurt <35:
    
15.         e = 3      
    
16.     hp_boss = 100
    
17.     hp_player = 100
    
18.     buff = []
    
19.     player = []
    
20. 
    
21.     for r in range(len(boss_skill)):  
    
22.         b = boss_skill[r]
    
23.         if buff:
    
24.             hp_player = min(hp_player+buff.pop(0),100)
    
25.         hp_boss = min(hp_boss+3,100)  
    
26.         if r == 0:                          # 第一回合
    
27.             if b=='普通攻击' or '致命一击':    # 如果boss的技能不是斩杀
    
28.                 player.append('搏命一击')
    
29.                 hp_player -= skill[b]+10
    
30.                 hp_boss -= 20
    
31.                 print 'boss:',b
    
32.                 print '玩家:','搏命击'
    
33.             else:                             # 如果boss 的技能是斩杀
    
34.                 player.append('治疗')
    
35.                 hp_player = min(hp_player+30,100)
    
36.                 buff = [10,10]
    
37.                 hp_player -= 45
    
38.                 print 'boss:',b
    
39.                 print '玩家:','治疗一次'
    
40.         else:                                # 第二回合以上
    
41.             if b=='斩杀':
    
42.                 player.append('躲闪')
    
43.                 print 'boss:',b
    
44.                 print '玩家:','躲闪一次'
    
45.             elif r % e == 0 and player[r-1] != '治疗':   #每隔 e 回合治疗一次，如果上回合使用了治疗，则这个回合不用治疗                              
    
46.                 player.append('治疗')
    
47.                 hp_player = min(hp_player+30,100)
    
48.                 buff = [10,10]
    
49.                 hp_player -= skill[b]
    
50.                 print 'boss:',b
    
51.                 print '玩家:','治疗一次'
    
52.             elif hp_player <=30 and player[r-1]!='治疗':   # 当血量小于30 时且上回合没有使用治疗时，治疗
    
53.                 player.append('治疗')
    
54.                 hp_player = min(hp_player+30,100)
    
55.                 buff = [10,10]
    
56.                 hp_player -= skill[b]
    
57.                 print 'boss:',b
    
58.                 print '玩家:','治疗一次'
    
59.             else:                                    # 否则  玩家  使用 搏命一击
    
60.                 player.append('搏命一击')
    
61.                 hp_player -= skill[b]+10
    
62.                 hp_boss -= 20
    
63.                 print 'boss:',b
    
64.                 print '玩家:','搏命一击'
    
65.    
    
66.         print('Round %d: Boss HP: %d, Player HP: %d' % \
    
67.                 (r+1, hp_boss, hp_player))
    
68.    
    
69.         if hp_player <= 0:
    
70.             return 'Player Lose! Round: %d' % (r+1),player
    
71.         if hp_boss <= 0:
    
72.             return 'Player Win! Round: %d' % (r+1),player

复制代码

[b][b][b]

五个boss技能列表，击杀boss所用回合分别为10,11,20,13,20[/b][/b][/b]