学步园

数字矩形

rectangle.pascal/c/cpp

【题目描述】

给一个由数字组成的矩形，每次可以向左、向右、向下走，求一条从最上层的任意一个点走到最下层的任意一个点最小数字和的路径，输出其值。

【输入】

输入第一行包含两个数n, m，表示矩形的行数和列数。

接下来的n行每行有m个数，每个数表示矩形该位置上的值。

【输出】

输出最上层的任意一个点走到最下层的任意一个点的最小数字和的路径值。

【输出样例】

3 4

9 9 1 9

2 2 2 9

1 9 9 9

【输出样例】

8

【样例解释】

9 9 19

2 2 2 9

1 9 9 9

是最优方案

【数据规模】

对于20%的数据，n, m不超过10

对于40%的数据，n * m不超过500

对于所有数据，n不超过100，m不超过500，每个数字不超过1000000。

题目描述很简单

状态很容易想出来，用 f [ i ] [ j ] 表示到位置 ( i , j ) 的最优值，但是有三个方向我们怎么转移呢？

我一开始的想法是不能，但是还是试着写了些，代码大概如下（错误的）

    for(int i=1;i<=n;i++)  
        for(int j=1;j<=m;j++)  
        {  
            f[i][j]=min(f[i][j],f[i-1][j]+map[i][j]);  
            if(j!=1) f[i][j]=min(f[i][j],f[i][j-1]+map[i][j]);  
            if(j!=m) f[i][j]=min(f[i][j],f[i][j+1]+map[i][j]);  
        }  

但是这样就有一个很严重的问题了，动态规划必须无后效性，然而我们退 f [ i ] [ j ] 的时候居然用到了它后面还没有计算的 f [ i ] [ j + 1 ] ！显然是不对的！

那应该如何处理呢？

我们可以分步递推，也就是先把所有从上一层下来的情况推倒完，再推到所有从左边走过来的情况，再推到所有从右边走过来的情况，这样每次推到都是相对独立的，最后求一个最小值即可

【注】考试WA了0.0，看到分析很简单，但没见这么处理的。这类题可推广否？

    /* 

http://blog.csdn.net/jiangzh7

    By Jiangzh 
    */  
    #include<cstdio>  
    #include<cstring>  
    #include<queue>  
    #include<utility>  
    using namespace std;  
    #define min(a,b) ((a)<(b)?(a):(b))  
    const int N=500+10;  
    const int inf=0x3f3f3f3f;  
      
    int n,m;  
    int map[N][N];  
    int f[N][N];  
      
    int main()  
    {  
        freopen("rectangle.in","r",stdin);  
        freopen("rectangle.out","w",stdout);  
        scanf("%d%d",&n,&m);  
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&map[i][j]);  
        memset(f,0x3f,sizeof(f));  
        for(int j=0;j<=m;j++) f[0][j]=0;  
        for(int i=1;i<=n;i++)  
        {  
            for(int j=1;j<=m;j++) f[i][j]=min(f[i][j],f[i-1][j]+map[i][j]);  
            for(int j=2;j<=m;j++) f[i][j]=min(f[i][j],f[i][j-1]+map[i][j]);  
            for(int j=m-1;j>0;j--) f[i][j]=min(f[i][j],f[i][j+1]+map[i][j]);  
        }  
        int ans=inf;  
        for(int j=1;j<=m;j++) ans=min(ans,f[n][j]);  
        printf("%d\n",ans);  
        return 0;  
    }