开发者社区> crazyacking> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

构造 - HDU 5402 Travelling Salesman Problem

简介:  Travelling Salesman Problem Problem's Link:  http://acm.hdu.edu.cn/showproblem.php?pid=5402   Mean:  现有一个n*m的迷宫,每一个格子都有一个非负整数,从迷宫的左上角(1,1)到迷宫的右下角(n,m),并且使得他走过的路径的整数之和最大,问最大和为多少以及他走的路径。
+关注继续查看

 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;
}
/*

*/

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
HDU-1048,The Hardest Problem Ever(字符串处理)
HDU-1048,The Hardest Problem Ever(字符串处理)
0 0
HDOJ/HDU 1022 Train Problem I(模拟栈)
HDOJ/HDU 1022 Train Problem I(模拟栈)
0 0
UESTC 1591 An easy problem A【线段树点更新裸题】
An easy problem A Time Limit: 2000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) Submit Status N个数排成一列,Q个询问,每次询问一段区间内的数的极差是多少。
746 0
HDU 1000 A + B Problem(指针版)
A + B Problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 654986    Accepted Submission(s): 204210 Problem Description Calculate A + B.
437 0
【OJ】Ants acmclub.com 10913 // poj 1852
#include #include #include using namespace std; int shu[1000010]; int main(){ int i,a,b; while(scanf("%d %d",&a,&b)!=EOF){ for(...
642 0
+关注
crazyacking
PaaS技术、Kubernetes、云计算,架构设计、数据库、数据结构、Unix/Linux编程
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载