题目大意：n*ｍ的格子，从左上角走到右下角,每个格子只能走一遍,每个格子上有一个非负数,要让途径的数字和最大，最后要输出路径
思路：显然茹果n,m有一个是奇数的话所有格子的数字都能被我吃到,如果都是偶数呢？我把棋盘黑白染色,显然其中染成黑色的点我都是能不取一个，剩下的点我每个都取．
比赛的时候gkp说能不能取两个白色的块反而比只取一个黑色块结果大，想了下是不会的，证明很简单，n,m都是偶数那么黑色块和白色快的数量是相同的，每次只能上下左右走，也就是只能从一个颜色走到另一个颜色，如果能够避开两块或者更多的黑块而不经过白块,那么经过格子的路线必然不能能出现黑白黑白的序列，发现这个后证实了我的想法,比赛时ＣＰ敲了这题的代码，下面是我赛后ＡＣ的
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 5000009
#define ll long long
using namespace std;
const int dx[]={,,,,-};
const int dy[]={,,-,,};
const char di[]={'','R','L','D','U'};
int a[][],n,m,d=,visit[][];
void dfs(int x,int y,int l,int r,int xt,int yt)
{
if(x==n && y==r)return;
d = (d%)+;
visit[x][y] = ;
for(int i=;i<=;i++)
{
int xx = x + dx[i], yy = y + dy[i];
if(xx<||xx>n||visit[xx][yy]||yy<l || yy > r ||(xx==xt && yy == yt))continue;
printf("%c",di[i]);
dfs(xx,yy,l,r,xt,yt);
d = i;
break;
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(visit,,sizeof(visit));
int sum = ;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
scanf("%d",&a[i][j]);
sum += a[i][j];
}
}
if(n&)
{
printf("%d\n",sum);
int u = (n-)>>;
while(u--)
{
for(int i=;i<m;i++)printf("R");
printf("D");
for(int i=;i<m;i++)printf("L");
printf("D");
}
for(int i=;i<m;i++)printf("R");
puts("");
}
else if(m&)
{
printf("%d\n",sum);
int u = (m-)>>;
while(u--)
{
for(int i=;i<n;i++)printf("D");
printf("R");
for(int i=;i<n;i++)printf("U");
printf("R");
}
for(int i=;i<n;i++)printf("D");
puts("");
}
else
{
int x=,y=,minx = 0x3f3f3f3f;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)if((i+j)&)
{
if(minx>a[i][j])
{
minx=a[i][j];
x=i;
y=j;
}
}
}
printf("%d\n",sum-minx);
int u = (y-)>>,t=u;
while(t--)
{
for(int i=;i<n;i++)printf("D");
printf("R");
for(int i=;i<n;i++)printf("U");
printf("R");
}
d=;
dfs(,u*+,u*+,u*+,x,y);
int v = m-u*-;
v>>=;t=v;
while(t--)
{
printf("R");
for(int i=;i<n;i++)printf("U");
printf("R");
for(int i=;i<n;i++)printf("D");
}
puts("");
}
}
return ;
}