2139.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2139 on 2006-07-23 at 15:59:23 */ 
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

typedef unsigned int uint;
const int H_MAX = 1024;
const int N_MAX = 64;
const int INF = 1 << 30;
const char *DIR = "UD";

int main()
{
	int n, build[N_MAX];
	uint hei[N_MAX][H_MAX];
	int sum[N_MAX], t, T, i, j;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n); sum[0] = 0;
		for(i = 0; i < n; i++) { scanf("%d", &build[i]); sum[i+1] = sum[i] + build[i]; }
		memset(hei, -1, sizeof(hei)); hei[0][0] = 0;
		for(i = 0; i < n; i++)
			for(j = 0; j <= sum[i]; j++) {
				if(hei[i][j] == UINT_MAX) continue;
				uint nowH = j+build[i], now = max(hei[i][j]>>1, nowH);
				hei[i+1][nowH] = min(hei[i+1][nowH], now<<1);
				if(j < build[i]) continue;
				nowH = j-build[i]; now = max(hei[i][j]>>1, nowH);
				hei[i+1][nowH] = min(hei[i+1][nowH], (now<<1)|1);
			}
		if(hei[n][0] == UINT_MAX) printf("IMPOSSIBLE\n");
		else {
			char dir[N_MAX] = ""; int nh = 0;
			for(i = n; i > 0; i--) {
				dir[i-1] = DIR[hei[i][nh]&1];
				nh += (dir[i-1] == 'U') ? -build[i-1] : build[i-1];
			}
			printf("%s\n", dir);
		}
	}
	
	return 0;
}