HDU5402 暴力模拟

因为题目中没有说是否是正整数，导致我们以为是DP，没敢做。。。太可惜了，不过现场赛绝对不会出现这种情况，毕竟所有的提问是都可以看见的。

题意：告诉一个矩阵，然后求从（1,1）到（n,m）能走过的最大和。

分析：如果行或者列是奇数，就可以全部遍历。否则就会只空出一个数的位置，这个位置一定在奇数行的偶数列，或者偶数行的奇数列[ （0~n-1//\0~m-1） ]。

偶数行奇数列奇数行偶数列

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <sstream>
  4 #include <cmath>
  5 #include <cstring>
  6 #include <cstdlib>
  7 #include <string>
  8 #include <vector>
  9 #include <map>
 10 #include <set>
 11 #include <queue>
 12 #include <stack>
 13 #include <algorithm>
 14 using namespace std;
 15 #define ll long long
 16 #define _cle(m, a) memset(m, a, sizeof(m))
 17 #define repu(i, a, b) for(int i = a; i < b; i++)
 18 #define repd(i, a, b) for(int i = b; i >= a; i--)
 19 #define sfi(n) scanf("%d", &n)
 20 #define pfi(n) printf("%d
", n)
 21 #define MAXN 100010
 22 int main()
 23 {
 24     int n,m,a;
 25     while(~scanf("%d%d",&n,&m))
 26     {
 27         int sum = 0,minn = MAXN,x = 0,y = 0;
 28         repu(i,0,n)
 29         repu(j,0,m)
 30         {
 31             scanf("%d",&a);
 32             sum += a;
 33             ///只比较偶数行，奇数列或者奇数行偶数列位置上的数字
 34             if(minn > a && (i+j)%2)
 35             {
 36                 x = i;
 37                 y = j;
 38                 minn = a;
 39             }
 40         }
 41         //cout<<minn<<" "<<x<<" "<<y<<endl;
 42         if (n%2==1)
 43         {
 44             printf("%d
",sum);
 45             repu(i,0,n/2)
 46             {
 47                 repu(j,0,m-1)
 48                 putchar('R');
 49                 putchar('D');
 50                 repu(j,0,m-1)
 51                 putchar('L');
 52                 putchar('D');
 53             }
 54             repu(j,0,m-1)
 55             putchar('R');
 56         }
 57         else if (m%2==1)
 58         {
 59             printf("%d
",sum);
 60             repu(i,0,m/2)
 61             {
 62                 repu(j,0,n-1)
 63                 putchar('D');
 64                 putchar('R');
 65                 repu(j,0,n-1)
 66                 putchar('U');
 67                 putchar('R');
 68             }
 69             repu(j,0,n-1)
 70             putchar('D');
 71         }
 72         else
 73         {
 74             printf("%d
",sum - minn);
 75             repu(i,0,x/2)
 76             {
 77                 repu(j,0,m-1)
 78                 putchar('R');
 79                 putchar('D');
 80                 repu(j,0,m-1)
 81                 putchar('L');
 82                 putchar('D');
 83             }
 84             repu(j,0,y/2)
 85             putchar('D'),putchar('R'),putchar('U'),putchar('R');
 86             if (x%2==1)
 87                 putchar('R'),putchar('D');
 88             else
 89                 putchar('D'),putchar('R');
 90             repu(j,y/2+1,m/2)
 91             putchar('R'),putchar('U'),putchar('R'),putchar('D');
 92             repu(i,x/2+1,n/2)
 93             {
 94                 putchar('D');
 95                 repu(j,0,m-1) putchar('L');
 96                 putchar('D');
 97                 repu(j,0,m-1) putchar('R');
 98             }
 99         }
100         puts("");
101     }
102     return 0;
103 }
104 /*
105 空了个3
106 6 6
107 1  13 14 15 20 21
108 16 12 11 10 22 23
109 9  8  7  6  24 26
110 5  4  3  2  25 27
111 28 29 30 31 32 33
112 34 35 36 17 18 19
113 */

View Code