URAL 1029 Ministry

URAL_1029

    dp。

#include<stdio.h>
#include<string.h>
#define MAXN 110
#define MAXM 510
int N, M, a[MAXN][MAXM], p[MAXN][MAXM];
long long f[MAXN][MAXM];
void init()
{
    int i, j;
    for(i = 1; i <= N; i ++)
        for(j = 1; j <= M; j ++)
            scanf("%d", &a[i][j]);
}
void dfs(int x, int y)
{
    if(p[x][y] == -1)
    {
        printf("%d", y);
        return ;
    }
    if(p[x][y] == 0)
        dfs(x - 1, y);
    else if(p[x][y] == 1)
        dfs(x, y - 1);
    else
        dfs(x, y + 1);
    printf(" %d", y);
}
void solve()
{
    int i, j, x, y;
    long long ans;
    for(i = 1; i <= M; i ++)
        f[1][i] = a[1][i], p[1][i] = -1;
    for(i = 2; i <= N; i ++)
    {
        for(j = 1; j <= M; j ++)
            f[i][j] = f[i - 1][j] + a[i][j], p[i][j] = 0;
        for(j = 2; j <= M; j ++)
            if(f[i][j - 1] + a[i][j] < f[i][j])
                f[i][j] = f[i][j - 1] + a[i][j], p[i][j] = 1;
        for(j = M - 1; j >= 1; j --)
            if(f[i][j + 1] + a[i][j] < f[i][j])
                f[i][j] = f[i][j + 1] + a[i][j], p[i][j] = 2;
    }
    ans = f[N][1], x = N, y = 1;
    for(i = 2; i <= M; i ++)
        if(f[N][i] < ans)
            ans = f[N][i], y = i;
    dfs(x, y);
    printf("\n");
}
int main()
{
    while(scanf("%d%d", &N, &M) == 2)
    {
        init();
        solve();
    }
    return 0;
}