Travelling Salesman Problem
Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=5402
Mean:
现有一个n*m的迷宫，每一个格子都有一个非负整数，从迷宫的左上角(1,1)到迷宫的右下角(n,m)，并且使得他走过的路径的整数之和最大，问最大和为多少以及他走的路径。
analyse:
首先，因为每个格子都是非负整数，而且规定每个格子只能走一次，所以为了使和尽可能大，必定是走的格子数越多越好。这样我们就需要考虑一下是不是所有的格子都可以走。
在纸上画画，你就会发现，若n、m中至少有一个是奇数的话，必然能够遍历每一个格子，这样的话，我们只需往n、m中为偶数的那个方向先走。
若n、m都为偶数的话，根据棋盘黑白染色(关于棋盘黑白染色问题，想了解的可以点链接)可以得知，当假设(1,1)与(n,m)都为黑色，那么这条路径势必黑色格子数会比白色格子数多1，而棋盘中黑白格子数是相等的，所以棋盘中有一个白格子不会被经过。
或许你自己在研究这道题的时候，会感觉有点混乱，总想着删值最小的格子，但有些格子删了，会有好几个格子走不到，那是因为删了黑格子的缘故，那样导致黑白格子数差2，又要有两个白格子无法到达，这样和势必会比只删一个白格子要来得小。
所以只能删白格子
Time complexity: O(N)
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-18-15.57
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
int n , m;
int a [ 110 ][ 110 ];
int main()
{
ios_base :: sync_with_stdio( false);
cin . tie( 0);
while( ~ scanf( "%d %d" , &n , & m))
{
LL sum = 0;
for( int i = 0; i <n; ++ i)
{
for( int j = 0; j < m; ++ j)
scanf( "%d" , & a [ i ][ j ]), sum += a [ i ][ j ];
}
bool flag = true;
if(n % 2 == 1|| m % 2 == 1)
{
printf( "%I64d \n " , sum);
if(n % 2 == 1)
{
for( int i = 0; i <n - 1; ++ i)
{
for( int j = 0; j < m - 1; ++ j)
printf( "%c" , flag ? 'R' : 'L');
printf( "%c" , 'D');
flag =! flag;
}
for( int i = 0; i < m - 1; ++ i) printf( "%c" , flag ? 'R' : 'L');
puts( "");
continue;
}
if( m % 2 == 1)
{
for( int i = 0; i < m - 1; ++ i)
{
for( int j = 0; j <n - 1; ++ j)
printf( "%c" , flag ? 'D' : 'U');
printf( "%c" , 'R');
flag =! flag;
}
}
for( int i = 0; i <n - 1; ++ i) printf( "%c" , flag ? 'D' : 'U');
puts( "");
continue;
}
// structure
int mi = INT_MAX , row , col;
for( int i = 0; i <n; ++ i)
{
for( int j = 0; j < m; ++ j)
{
if((( i + j) % 2 == 1) && a [ i ][ j ] < mi)
mi = a [ i ][ j ], row = i , col = j;
}
}
printf( "%I64d \n " , sum - mi);
flag = true;
for( int i = 0; i <n; ++ i)
{
if( i <= row - 2)
{
for( int j = 0; j < m - 1; ++ j)
printf( "%c" , flag ? 'R' : 'L');
printf( "%c" , 'D' ), flag =! flag;
}
else break;
}
bool ff = true;
if( flag)
{
for( int j = 0; j < m - 1; ++ j)
{
if( j != col)
{
printf( "%c" , ff ? 'D' : 'U' ), ff =! ff;
}
printf( "%c" , flag ? 'R' : 'L');
}
}
else
{
for( int j = m - 1; j > 0; -- j)
{
if( j != col)
printf( "%c" , ff ? 'D' : 'U' ), ff =! ff;
printf( "%c" , flag ? 'R' : 'L');
}
}
flag =! flag;
if( ff) printf( "%c" , 'D');
for( int i =( row == 0) ? row + 2 : row + 1; i <n; ++ i)
{
printf( "D");
for( int j = 0; j < m - 1; ++ j)
printf( "%c" , flag ? 'R' : 'L');
flag =! flag;
}
puts( "");
}
return 0;
}
/*
*/
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-18-15.57
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std;
int n , m;
int a [ 110 ][ 110 ];
int main()
{
ios_base :: sync_with_stdio( false);
cin . tie( 0);
while( ~ scanf( "%d %d" , &n , & m))
{
LL sum = 0;
for( int i = 0; i <n; ++ i)
{
for( int j = 0; j < m; ++ j)
scanf( "%d" , & a [ i ][ j ]), sum += a [ i ][ j ];
}
bool flag = true;
if(n % 2 == 1|| m % 2 == 1)
{
printf( "%I64d \n " , sum);
if(n % 2 == 1)
{
for( int i = 0; i <n - 1; ++ i)
{
for( int j = 0; j < m - 1; ++ j)
printf( "%c" , flag ? 'R' : 'L');
printf( "%c" , 'D');
flag =! flag;
}
for( int i = 0; i < m - 1; ++ i) printf( "%c" , flag ? 'R' : 'L');
puts( "");
continue;
}
if( m % 2 == 1)
{
for( int i = 0; i < m - 1; ++ i)
{
for( int j = 0; j <n - 1; ++ j)
printf( "%c" , flag ? 'D' : 'U');
printf( "%c" , 'R');
flag =! flag;
}
}
for( int i = 0; i <n - 1; ++ i) printf( "%c" , flag ? 'D' : 'U');
puts( "");
continue;
}
// structure
int mi = INT_MAX , row , col;
for( int i = 0; i <n; ++ i)
{
for( int j = 0; j < m; ++ j)
{
if((( i + j) % 2 == 1) && a [ i ][ j ] < mi)
mi = a [ i ][ j ], row = i , col = j;
}
}
printf( "%I64d \n " , sum - mi);
flag = true;
for( int i = 0; i <n; ++ i)
{
if( i <= row - 2)
{
for( int j = 0; j < m - 1; ++ j)
printf( "%c" , flag ? 'R' : 'L');
printf( "%c" , 'D' ), flag =! flag;
}
else break;
}
bool ff = true;
if( flag)
{
for( int j = 0; j < m - 1; ++ j)
{
if( j != col)
{
printf( "%c" , ff ? 'D' : 'U' ), ff =! ff;
}
printf( "%c" , flag ? 'R' : 'L');
}
}
else
{
for( int j = m - 1; j > 0; -- j)
{
if( j != col)
printf( "%c" , ff ? 'D' : 'U' ), ff =! ff;
printf( "%c" , flag ? 'R' : 'L');
}
}
flag =! flag;
if( ff) printf( "%c" , 'D');
for( int i =( row == 0) ? row + 2 : row + 1; i <n; ++ i)
{
printf( "D");
for( int j = 0; j < m - 1; ++ j)
printf( "%c" , flag ? 'R' : 'L');
flag =! flag;
}
puts( "");
}
return 0;
}
/*
*/
