hdu 5569 DP

野性酷女 2022-08-17 16:07 129阅读 0赞

题意：

有一个n行m列的矩阵，其中n+m为奇数。

现在从（1,1）到（n，m）一共要走2×k步，分别为a1，a2......a2×k。

总的代价为a1×a2+a3×a4+......+a(2\*k-1)\*a(2\*k);

求所有可能的路径中，代价最小的，输出代价

思路和过程见代码注释。

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    using namespace std;
    
    const int maxn = 1005;
    
    int n,m;
    int a[maxn][maxn];
    int dp[maxn][maxn];//dp[i][j] 为从（1，1）到（i,j）的最短路程i+ j为奇数
    
    int main()
    {
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            for(int i = 1 ; i <= n ; i++)
            {
                for(int j = 1 ; j <= m ; j++)
                {
                    scanf("%d",&a[i][j]);
                }
            }
            memset(dp,0x3f,sizeof(dp));
            dp[0][1] = dp[1][0] = 0 ;
            for(int i = 2 ; i <= m ; i++)
            {
                dp[1][i]=dp[1][i-2]+a[1][i-1]*a[1][i];//第一列
            }
            for(int i = 2 ; i <= n ; i++)
            {
                dp[i][1]=dp[i-2][1]+a[i-1][1]*a[i][1];//第一行
            }
            for(int i = 2 ; i <= n ; i++)
            {
                for(int j = 2 ; j <= m ; j++)
                {
                    if((i+j)&1)
                    {
                        dp[i][j]=min(dp[i][j],min(min(dp[i-2][j]+a[i-1][j]*a[i][j],dp[i][j-2]+a[i][j-1]*a[i][j]),
                        dp[i-1][j-1]+min(a[i][j-1]*a[i][j],a[i-1][j]*a[i][j])));
                    }
                }
            }
            printf("%d\n",dp[n][m]);
        }
        return 0;
    }
    
    
    /*
    Auther:LIUYAN
    2015.11.30
    思路：dp[i][j] 为从（1，1）到（i,j）的最短路程i+ j为奇数
    DP[i][j]可有dp[i][j-2]+a[i][j-1]*a[i][j]或者dp[i-2][j]+a[i-1][j]*a[i][j]
    或者dp[i-1][j-1]+a[i][j-1]*a[i][j]或者dp[i-1][j-1]+a[i-1][j]*a[i][j];
    求出其中的最小值就可以了。
    */