Ural_1026.Ministy (DP)

　　/*昨天看这题，没思路。今天开始做这题，WA到爆了！NND， 把M和N的大小整反
了。一遍一遍的盯着我的程序看，苍天啊！浪费生命啊！

思路：

　　转移方程：dp[i][j] = min(dp[i-1][j], dp[i][j+1], dp[i][j-1]) + a[i][j];

然后把j从前往后，和从后往前分别走一遍。（只一遍的话实现不了转移方程）
另外开一个数组记录到达(i, j)，这个位置时过来的方向。最后顺着过来的方向，入队列，输
出。
我是直接从后往前推的，输出方便。*/

//My Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define l -1
#define r -2
#define d 0
using namespace std;

const int N = 110;
const int M = 510;

long long dp[N][M];
int a[N][M];
int  dir[N][M];
int pre[M*10];

int main() {
    //freopen("data.in", "r", stdin);

    int m, n, i, j, k, y;
    scanf("%d%d", &m, &n);

    for(i = m; i >= 1; i--)
        for(j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);

    for(i = 1; i <= n; i++){
        dp[1][i] = a[1][i];
        dir[1][i] = d;
    }

    for(i = 2; i <= m; i++) {
        for(j = 1; j <= n; j++) {
            dp[i][j] = dp[i-1][j] + a[i][j];
            dir[i][j] = d;
        }
    }
    for(i = 2; i <= m; i++) {
        for(j = 1; j <= n; j++) {    //从前往后一遍
            if(j == 1) {
                if(dp[i][j] > dp[i-1][j] + a[i][j]) {
                    dp[i][j] = dp[i-1][j] + a[i][j];
                    dir[i][j] = d;
                }
            } else {
                if(dp[i][j] > min(dp[i][j-1], dp[i-1][j]) + a[i][j]) {
                    dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + a[i][j];
                    if(dp[i][j-1] < dp[i-1][j])    dir[i][j] = l;
                    else    dir[i][j] = d;
                }
            }
        }
        for(j = n; j >= 1; j--) {    //从后往前再来一遍
            if(j == n) {
                if(dp[i][j] > dp[i-1][j] + a[i][j]) {
                    dp[i][j] = dp[i-1][j] + a[i][j];
                    dir[i][j] = d;
                }
            } else {
                if(dp[i][j] > min(dp[i][j+1], dp[i-1][j]) + a[i][j]) {
                    dp[i][j] = min(dp[i][j+1], dp[i-1][j]) + a[i][j];
                    if(dp[i][j+1] < dp[i-1][j])    dir[i][j] = r;
                    else    dir[i][j] = d;
                }
            }
        }
    }
    for(y = 1, i = 2; i <= n; i++)
        if(dp[m][i] < dp[m][y])
            y = i;

    k = 0;     pre[k++] = y;    //顺着方向找对应的位置
    while(m != 1) {
        if(dir[m][y] == l)    y--;
        else if(dir[m][y] == r)    y++;
        else if(dir[m][y] == d)    m--;
        pre[k++] = y;
    }
    for(i = 0; i < k-1; i++)
        printf("%d ", pre[i]);
    printf("%d\n", pre[i]);
    return 0;
}