飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=995

题意：就是给你n个数，它们的和不超过1000，接着就是你可以选择加或则减，就是说初始值是0，然后n步，你可以选择加上第i个数，或则减掉第i个数，但是减掉的时候不能小于0。求最后的数字是0，且使的加到的最大值最小。求出这个路径。

分析：这个题，刚开始的想法是，先是想想加加减减看看最后能不能到达0，那么直接可以用dp，因为有加又有减，所以一维数组就很难维护了，这里我就用二维数组，dp[i][j]表示第i个数过后，能不能到达j这个高度，那么看最后能不能成为0，就是能不能到达dp[n][0]了这样可以轻易的求出能不能到达0，但是现在我们需要知道最大值最小，所以需要维护点东西，这里分2中情况（这里定义ai为第i个数的大小）

(1)假设i-1能到达j，那么i肯定能到达j+ai[i]，然后我们需要更新到达j+ai[i]的最大值，假设dp[i-1][j]为i-1过后，到达j的最大值的最小值，那么如果j+ai[i]>dp[i-1][j]的话，那么就得更新最大值的最小值，因为我们必须到达j+ai[i]，反之的话就是dp[i-1][j]，设这个值为qn，这个值是从dp[i-1][j]推过来的，所以更新dp[i][j+ai[i]]=min(dp[i][j+ai[i]],qn),这样高度最小

(2)假设i-1能到达j，且j-ai[i]>=0,那么肯定能到达j-ai[i],接着我们就可以根据第一种情况dp，但是有个地方不同，这里比较的是j和dp[i-1][j]，因为j-ai[i]<j;接着就是跟第一种情况一样,设这里的只为pn,则dp[i][j-ai[i]]=min(dp[i][j-ai[i]],pn),

根据这两种我们就知道最大值最小是什么样的情况，最后需要输出，只要用一个数组li来记录，具体怎么记录?第一种情况,如果dp[i][j+ai[i]]比原来的数要小，那么就是li[i][j+ai[i]]指向i-1的j，另一种情况就是li[i][j-ai[i]]只想i-1的j,最后反推就是答案了，然后啪啪啪就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=1234;
int ai[maxn];
int dp[maxn][maxn];
int li2[maxn][maxn];
int T;
int n;
void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)scanf("%d",&ai[i]);
}
vector<int> V;
void play()
{
    for(int i=0; i<=n; i++)
    {
        for(int j=0; j<=1000; j++)
        {
            dp[i][j]=INF;
        }
    }
    dp[0][0]=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<=1000; j++)
        {
            if(dp[i-1][j]==INF)continue;
            int q=j+ai[i];
            int p=j-ai[i];
            int qn=max(dp[i-1][j],q);
            if(q<=1000&&qn<dp[i][q])
            {
                dp[i][q]=qn;
                li2[i][q]=j;
            }
            int pn=max(dp[i-1][j],j);
            if(p>=0&&pn<dp[i][p])
            {
                dp[i][p]=pn;
                li2[i][p]=j;
            }
        }
    }
    if(dp[n][0]!=INF)
    {
        V.clear();
        V.push_back(2);
        int st=n-1;
        int now=li2[n][0];
        while(st>=1){
            int next=li2[st][now];
            int ff=now-next;
            if(ff>0)V.push_back(1);
            else V.push_back(2);
            st--;
            now=next;
        }
        bool first=1;
        for(int i=V.size()-1;i>=0;i--){
            if(V[i]==1)printf("U");
            else printf("D");
        }
        printf("\n");
    }
    else
    {
        printf("IMPOSSIBLE\n");
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}