[題目描述]

在著名游戲“冰與火之歌”中英雄們親自參戰了！英雄一開始有HP_H點生命值與MP_H點魔法值，英雄們能夠使用不同的技能，你的英雄會三種技能：雷霆之怒、混沌轉移和天使之心。

英雄要打一群怪獸，每只怪獸一開始有HP_M點生命值，這一群怪獸一開始有N_M只，它們的總生命值就有HP_M×N_M點，隨著戰斗的進行，怪獸群的總生命值減少。假設當前怪獸群有H點總生命值，那么還存活的怪獸個數為H/HP_M取上整。

戰斗在一個一維的包含N+1個格子的戰場上進行，格子從0開始編號，你的英雄一直在0號格子不動，怪獸們一開始在N號格子并且可以移動，怪獸們一回合最多移動V個格子。

戰斗是回合制的，你的英雄是先手，英雄與怪獸輪換進行，怪獸的策略非常簡單，它們先往英雄的方向移動min(V，P-1)格，P為它們在回合一開始所在的格子的編號，如果怪獸們在移動之后到達了1號格子，那么它們就會攻擊你的英雄，如果有K只怪獸進行攻擊，你的英雄就會扣掉K點生命值，如果你的英雄的生命值變為了非正數，那么這場戰斗就失敗了。

在你的英雄的回合，他必須要施展三種技能中的一種，三個技能的效果如下：

雷霆之怒：減少怪物群LP點生命值，P為怪物們所在的格子的編號。

混沌轉移：把怪物群傳送到任何一個格子（不能為0號）。

天使之心：你的英雄恢復dH點生命值，但是不能超過初始生命值。

施展任何一種技能都需要消耗1點魔法值，當怪物群的生命值降為0時，你的英雄取得勝利。

給出一種初始局面，請你判斷你的英雄是否有獲得勝利的策略，如果有，請輸出任何一種勝利的決策方案。

[數據范圍]

1 ≤N ≤ 10, 2 ≤ HP_H ≤ 100, 1 ≤ MP_H ≤ 50, 1 ≤ HP_M ≤10, 1 ≤ N_M ≤ 10, 1 ≤ V ≤ N, 1 ≤ dH < HP_H，1 ≤ L_i ≤ 10

[題解]

? ? ? ? 這道題正解應該是搜索或者dp,不過我考場上由于上一道題打了模擬退火,所以就用遺傳算法做了一下(雖然這兩個東西似乎沒什么聯系).第一次用遺傳算法,各種WA,不過主要是因為題目意思沒有理解清楚,遺傳算法的部分其實不難.

? ? ? ? 我是以英雄死前能對怪獸造成的最大傷害來評價一個個體的優劣的.產生下一代的方法是:最優的10個個體直接進入下一輪遺傳,再選10對個體隨機交配,交配的個體分別將自己一半的基因給子代,子代在其基因片段中隨出若干個片段產生變異,這里我借鑒模擬退火的方法,隨機的次數越多,選擇的變異片段越少.實際的評測效果很好,有很大的幾率能夠AC,我最少也隨出85分.另外,初始時的個體應該可以貪心搞出一些優秀的個體,這樣的話算法的正確性會進一步提升.(由于評測機器的差異,可能要減少循環次數)

? ? ? ? 在排序的過程中,我用的是選擇排序.為了避免數組的交換,我直接定義了兩個指針來加速.

Code:

program heroes; typeint=longint;arr=array[1..50]of char;point=^arr;arr2=array[1..50]of int;p2=^arr2; const skill:array[0..2]of char=('L','T','H'); vari,j,k,m,n,ii,t:int;ok:boolean=false;h_h,m_h,n_m,h_m,v_m,dh,h_tot_m:int;lp,next:array[1..20]of int;f:array[1..20]of arr;g:array[1..20]of arr2;p:array[1..20]of point;q:array[1..20]of p2;harm:array[1..20]of int;aa:array[1..120000]of int;po1:point;po2:p2;function min(x,y:int):int; beginif x<y then exit(x)else exit(y); end;function get(p:point;q:p2):int;var i,j,h,m:int;//計算個體適應度 beginget:=0;h:=h_h;m:=n;for i:=1 to m_h do beginif p^[i]='L'then inc(get,lp[m])else if p^[i]='H'then begin inc(h,dh);if h>h_h then h:=h_h;endelse if p^[i]='T'then m:=q^[i];m:=next[m];if m=1 then beginh:=h-trunc((h_tot_m-get+h_m-1)/h_m);if h<=0 then break;end;end; end;procedure sort;//排序 beginfor i:=1 to 20 do begink:=i;for j:=i+1 to 20 do if(harm[j]>harm[k])then k:=j;po1:=p[i];p[i]:=p[k];p[k]:=po1;po2:=q[i];q[i]:=q[k];q[k]:=po2;t:=harm[k];harm[k]:=harm[i];harm[i]:=t;end; end;procedure new(f:point;g:p2);var i,x:int;//生成后代 beginx:=random(10)+1;for i:=1 to m_h>>1 do begin f^[i]:=p[x]^[i];g^[i]:=q[x]^[i];end;x:=random(10)+1;for i:=m_h>>1+1 to m_h do begin f^[i]:=p[x]^[i];g^[i]:=q[x]^[i];end;for i:=1 to aa[ii] do beginx:=random(m_h)+1;f^[x]:=skill[random(3)];if f^[x]='T'then g^[x]:=random(n)+1 else g^[x]:=0;end; end;procedure main;//進行篩選 beginfor i:=1 to 20 do harm[i]:=get(@f[i],@g[i]);for i:=1 to 20 do begin p[i]:=@f[i];q[i]:=@g[i];end;for i:=1 to 45000 do aa[i]:=trunc((100000-i)/10000)+1;for ii:=1 to 45000 do beginsort;if harm[1]>=h_tot_m then begin ok:=true;exit;end;for i:=10 to 20 do new(p[i],q[i]);for i:=10 to 20 do harm[i]:=get(p[i],q[i]);end; end;procedure print(x:int);var harm:int;//輸出 beginwriteln('VICTORIOUS');get(p[x],q[x]);harm:=0;m:=n;for i:=1 to m_h do beginwrite(p[x]^[i]);if p[x]^[i]='T'then writeln(' ',q[x]^[i])else writeln;if p[x]^[i]='L'then inc(harm,lp[m]);if p[x]^[i]='T'then m:=q[x]^[i];m:=next[m];if(harm>=h_tot_m)then exit;end; end;beginrandomize;assign(input,'heroes.in');reset(input);assign(output,'heroes.out');rewrite(output);read(n,h_h,m_h,h_m,n_m,v_m,dh);h_tot_m:=h_m*n_m;for i:=1 to n do read(lp[i]);for i:=1 to n do next[i]:=i-min(v_m,i-1);for i:=1 to 20 dofor j:=1 to m_h do beginf[i,j]:=skill[random(3)];if f[i,j]='T'then g[i,j]:=random(n)+1;end;next[1]:=1;main;if ok then beginfor i:=1 to 20 do if harm[i]>=h_tot_m then begin print(i);break;end;end else write('DEFEATED');close(input);close(output); end.

BY QW

轉載請注明出處

總結

以上是生活随笔為你收集整理的[遗传算法]冰与火之歌的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。