想法就是A[i][j]记录 走i+1步是否能到达j的高度，如果能到，记录其中高度最小的和最后一步的方向。
看A[i][j-p[i+1]]和A[i][j+p[i+1]]决定A[i+1][j]。

#include <math.h>
#include <iostream>
using namespace std;  
struct point
{
	int height;
	char dir;
};
void plan(int *p,int len)
{
	int i,j=0;
	float h=1000;
//	for (i=0;i<len;i++)
	//{
		//h=h+p[i];
	//}
//	h=ceil(h/2)+1;
	point **A;
	A=(point **)malloc((len)*sizeof(point *));
	for (i=0;i<len;i++)
	{
		A[i]=(point *)malloc(h*sizeof(point));
	}
	for(i=0;i<len;i++)
	{
		for (j=0;j<h;j++)
		{
			A[i][j].height=0;
			A[i][j].dir=' ';
		}
	}
	A[0][p[0]].height=p[0];
	A[0][p[0]].dir='U';
	for (i=1;i<len;i++)
		for (j=0;j<h;j++)
			if(j-p[i]>=0 && A[i-1][j-p[i]].height>0)
			{
				A[i][j].height=max(j,A[i-1][j-p[i]].height);
			    A[i][j].dir='U';
			}
			else if(j+p[i]<h && A[i-1][j+p[i]].height>0)
			{
				if(A[i][j].height>0)
				{
					A[i][j].height=min(A[i][j].height,A[i-1][j+p[i]].height);
					if(A[i][j].height==A[i-1][j+p[i]].height)
						A[i][j].dir='D';
				}
				else
				{
					A[i][j].height=A[i-1][j+p[i]].height;
				    A[i][j].dir='D';
				}
				
			}
	if (A[len-1][0].height==0)
	{
		cout<<"IMPOSSIBLE"<<endl;
	}
	else
	{
		char *result;
		result=(char*)malloc(len*sizeof(char));
		int temp=0;
		for (i=0;i<len;i++)
		{
			result[len-1-i]=A[len-1-i][temp].dir;
			if(result[len-1-i]=='U')
			{
				temp=temp-p[len-1-i];				
			}
			else
			{
				temp=temp+p[len-1-i];
			}
		}
		for (i=0;i<len;i++)
			cout<<result[i];
		cout<<endl;
	}
}


int main()
{
	int num_ins;
	cin>>num_ins;
	while(num_ins>0)
	{
		num_ins--;
		int len;
		cin>>len;
		int *height;
		height=(int*)malloc(len*sizeof(int));
		int i;
		for (i=0;i<len;i++)
		{
			cin>>height[i];
		}
		plan(height,len);
	}
	return 0;
}