Codeforces 6 D. Lizards and Basements 2

問題

n体の敵がいて、それぞれのHPはh[i]である。
魔法を敵iに向けて放つと、敵iにaのダメージを与え、（もし隣がいるなら）隣にもbずつのダメージを与える。

敵1と敵nには直接魔法を放つことはできない。
全ての敵のHPを0より小さくするのに必要な魔法の回数、
およびそのときの対象をどれか1通り出力せよ。

制約条件

3≦n≦10
h[i]≦15

方針

DP+経路復元。

今魔法で狙っている敵+右側3体のHPを覚えておく。すなわち、
dp[i][h1][h2][h3]を、i番目の敵を狙っていて（i-2番目までの敵は全て倒してある）
i-1番目がh1のHPで、i番目がh2のHPで、i+1番目がh3のHPであるような状態における、
魔法の最小詠唱回数とする。

ソースコード

なんか汚い。

int n,a,b,h[15];
int dp[20][20][20][20],prev[20][20][20][20];
void run()
{
	cin>>n>>a>>b;
	rep(i,n)cin>>h[i], h[i]++;
	h[n]=0;
	rep(i,20)rep(j,20)rep(k,20)rep(l,20)dp[i][j][k][l]=inf;
	dp[1][h[0]][h[1]][h[2]]=0;
	for(int i=1;i<n-1;i++)for(int h2=19;h2>=0;h2--)
	for(int h1=19;h1>=0;h1--)for(int h3=19;h3>=0;h3--)if(dp[i][h1][h2][h3]!=inf){
		int nh1=max(0,h1-b), nh2=max(0,h2-a), nh3=max(0,h3-b);
		if(nh1==0){
			if(dp[i+1][nh2][nh3][h[i+2]]>dp[i][h1][h2][h3]+1){
				dp[i+1][nh2][nh3][h[i+2]]=dp[i][h1][h2][h3]+1;
				prev[i+1][nh2][nh3][h[i+2]]=i*20*20*20+h1*20*20+h2*20+h3;
			}
		}
		if(dp[i][nh1][nh2][nh3]>dp[i][h1][h2][h3]+1){
			dp[i][nh1][nh2][nh3]=dp[i][h1][h2][h3]+1;
			prev[i][nh1][nh2][nh3]=i*20*20*20+h1*20*20+h2*20+h3;
		}
		if(h1==0){
			if(dp[i+1][h2][h3][h[i+2]]>dp[i][h1][h2][h3]){
				dp[i+1][h2][h3][h[i+2]]=dp[i][h1][h2][h3];
				prev[i+1][h2][h3][h[i+2]]=prev[i][h1][h2][h3];
			}
		}
	}
	cout<<dp[n-1][0][0][0]<<endl;
	int h1=0,h2=0,h3=0,p=n-1;
	while(h1!=h[0]||h2!=h[1]||h3!=h[2]||p!=1){
		int prv=prev[p][h1][h2][h3];
		int nh1=prv/20/20%20, nh2=prv/20%20, nh3=prv%20, np=prv/20/20/20;
		cout<<np+1<<" ";
		h1=nh1; h2=nh2; h3=nh3; p=np;
	}
	cout<<endl;
}