POJ 3003 Spiderman’s workout

問題

n個の上り下りの記録が与えられる。
それぞれの数字は上り下りの距離であるが、その方向はわからない。

最初は0mの高さにいて、全ての上り下りを終えた時点でも0mの高さにいる。
上り下りの途中で高さが0mを下回ることはない。
この条件を満たす上で、途中の最大の高さが最も小さくなるように上り下りする。

そのような上り下りの仕方をどれか一つ出力せよ。
一つもない場合、IMPOSSIBLEを出力せよ。

制約条件

n≦40
上り下りの総距離≦1000

方針

dp[i][j]をi番目の上り下りを終えた時点でjmの地点にいるときの、今までで上ったもっとも高い高さとする。
これを更新していくようなDPをすれば答えが求まる。

ソースコード

int dp[41][1001],prev[41][1001];
char ans[50];
int main()
{
	int cs; scanf("%d",&cs);
	while(cs--){
		int n,h[40];
		scanf("%d",&n);
		rep(i,n)scanf("%d",h+i);
		rep(i,n+1)rep(j,1001)dp[i][j]=inf;
		dp[0][0]=0;
		rep(i,n)rep(j,1001){
			if(j+h[i]<=1000&&dp[i+1][j+h[i]]>max(j+h[i],dp[i][j]))
			prev[i+1][j+h[i]]=j, dp[i+1][j+h[i]]=max(j+h[i],dp[i][j]);
			if(j-h[i]>=0&&dp[i+1][j-h[i]]>dp[i][j])
			prev[i+1][j-h[i]]=j, dp[i+1][j-h[i]]=dp[i][j];
		}
		if(dp[n][0]==inf)puts("IMPOSSIBLE");
		else{
			ans[n]=0;
			int t=0;
			for(int i=n-1;i>=0;i--){
				ans[i]=prev[i+1][t]<t?'U':'D';
				t=prev[i+1][t];
			}
			puts(ans);
		}
	}
	return 0;
}