点击打开vjudge题目链接

其实是水题一道,不过就是特判多一些,全是ifelse,比赛时晕了….

就是找最大的路径,当n和m有个奇数是比较好处理,从起点到终点走蛇形走完就好了。当n和m都是偶数的时候,画画图就可以看出,标号i+j是奇数的地方最多会有一个走不到,其他地方都会走到,所以找出i+j是奇数的最小值,然后不走它就是了。剩下的就是各种条件特判了,写的我都晕了…

C++代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;
int n, m, sum, v[maxn][maxn];

void input() {
    sum = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j) {
            scanf("%d", &v[i][j]);
            sum += v[i][j];
        }
}


void solve(int x, int y) {
    // printf("%d, %d---\n", x, y);
    int bg = (x % 2 ? x - 1 : x);
    for(int i = 0; i < n; i += 2) {
        if(i < bg) {
            for(int j = 0; j < m-1; ++j)
                putchar('R');
            putchar('D');
            for(int j = 0; j < m-1; ++j)
                putchar('L');
            if(i < n-2) putchar('D');
        }
        else if(i > bg) {
            for(int j = 0; j < m-1; ++j)
                putchar('L');
            putchar('D');
            for(int j = 0; j < m-1; ++j)
                putchar('R');
            if(i < n-2) putchar('D');
        }
        else if(i == bg) {
            for(int j = 0; j < y; ++j) {
                if(j % 2) putchar('U');
                else putchar('D');
                if(j < m-1) putchar('R');
            }
            if(y < m-1) putchar('R');
            for(int j = y+1; j < m; ++j) {
                if(j % 2) putchar('D');
                else putchar('U');
                if(j < m-1) putchar('R');
            }
            if(i < n-2) putchar('D');
        }
    }
}

int main() {
    while(~scanf("%d%d", &n, &m)) {
        input();
        if(m % 2) {
            printf("%d\n", sum);
            for(int i = 0; i < m; ++i) {
                if(i % 2 == 0) {
                    for(int j = 0; j < n-1; ++j)
                        putchar('D');
                } else {
                    for(int j = 0; j < n-1; ++j)
                        putchar('U');
                }
                if(i != m-1) putchar('R');
            }
        }
        else if(n % 2) {
            printf("%d\n", sum);
            for(int i = 0; i < n; ++i) {
                if(i % 2 == 0) {
                    for(int j = 0; j < m-1; ++j)
                        putchar('R');
                } else {
                    for(int j = 0; j < m-1; ++j)
                        putchar('L');
                }
                if(i != n-1) putchar('D');
            }
        } else {
            int x, y, best = INT_MAX;
            for(int i = 0; i < n; ++i)
                for(int j = 0; j < m; ++j) {
                    if ((i + j) % 2 == 1 && v[i][j] < best)
                        best = v[i][j], x = i, y = j;
                }
            printf("%d\n", sum-best);
            solve(x, y);
        }
        printf("\n");
    }
    return 0;
}

欢迎留言