Mars_Cat

啊。这道题好大。听说是杜教出的。。%%%%

题目如下：

Travelling Salesman Problem

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 34    Accepted Submission(s): 2
Special Judge
 

题目简述：从[1,1]到[n,m]，每个格子只能进入一次，使进入的格子权值之和最大

这道题经过精密的模拟测试，发现当n或m为奇数时可以全都跑遍。
然而当n,m均为偶数时，a[i][j](i+j为奇数时的格子可以被单独绕过，i+j为偶数时他必定会牵连到其他格子，为了使答案最大，那么我们就要选取i+j为奇数的格子中权值最小的。

于是这道题就解决了。

#define _CRT_SECURE_NO_WARNINGS

#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

typedef long long LL;

void Main();
int main()
{
	Main();
	return 0;
}
int n, m;
int a[110][110];
int tot, minn;
int xx, yy;

void Main()
{
	while (scanf("%d%d", &n, &m) != EOF)
	{
		tot = 0; minn = 10010;
		for (int i = 1;i <= n;++i)
			for (int j = 1;j <= m;++j)
			{
				scanf("%d", &a[i][j]);
				tot += a[i][j];
				if ((i + j) & 1)
				{
					if (minn > a[i][j])
					{
						minn = a[i][j];
						xx = i; yy = j;
					}
				}
			}
		if (n & 1)
		{
			printf("%d\n", tot);
			for (int i = 1;i <= n / 2;++i)
			{
				for (int j = 1;j <= m - 1;++j)printf("R");
				printf("D");
				for (int j = 1;j <= m - 1;++j)printf("L");
				printf("D");
			}
			for (int j = 1;j <= m - 1;++j)printf("R");
			puts("");
			continue;
		}
		if (m & 1)
		{
			printf("%d\n", tot);
			for (int i = 1;i <= m / 2;++i)
			{
				for (int j = 1;j <= n - 1;++j)printf("D");
				printf("R");
				for (int j = 1;j <= n - 1;++j)printf("U");
				printf("R");
			}
			for (int j = 1;j <= n - 1;++j)printf("D");
			puts("");
			continue;
		}
		if (yy & 1)
		{
			printf("%d\n", tot - minn);
			for (int i = 1;i <= ((yy - 1) >> 1);++i)
			{
				for (int j = 1;j <= n - 1;++j)printf("D");
				printf("R");
				for (int j = 1;j <= n - 1;++j)printf("U");
				printf("R");
			}
			printf("R");
			for (int i = 1;i <= ((xx - 1) >> 1);++i)printf("DLDR");
			printf("D");
			for (int i = 1;i <= (n - xx) / 2;++i)printf("DLDR");
			for (int i = 1;i <= (m - yy) / 2;++i)
			{
				printf("R");
				for (int j = 1;j <= n - 1;++j)printf("U");
				printf("R");
				for (int j = 1;j <= n - 1;++j)printf("D");
			}
			puts("");
		}
		else
		{
			printf("%d\n", tot - minn);
			for (int i = 1;i <= ((yy - 1) >> 1);++i)
			{
				for (int j = 1;j <= n - 1;++j)printf("D");
				printf("R");
				for (int j = 1;j <= n - 1;++j)printf("U");
				printf("R");
			}
			for (int i = 1;i <= ((xx - 1) >> 1);++i)printf("RDLD");
			printf("D");
			for (int i = 1;i <= ((n - xx - 1) >> 1);++i)printf("RDLD");
			printf("R");
			for (int i = 1;i <= (m - yy) / 2;++i)
			{
				printf("R");
				for (int j = 1;j <= n - 1;++j)printf("U");
				printf("R");
				for (int j = 1;j <= n - 1;++j)printf("D");
			}
			puts("");
		}
	}
	return;
}