hdu5569 BestCoder Round #63 (div.2)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：

给你一个矩阵，要求从左上角走到右下角，走个的费用：a[1]*a[2] + a[3]*a[4] + ......+ a[2n-1]*a[2n]

思路：

果然不机智，自己把自己套路了

对于每个奇数点，如下图的有下角的点它便可由3个值为2的点到达，具体画图便知。

所以我们可以用类似dp的方法，找出每个点的奇数点最优解，注意下边界即可

1 1 1 2

1 1 2 1

1 2 1 1

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <algorithm>

const int inf = 0x3f3f3f3f;

using namespace std;

typedef long long ll;

ll a[1005][1005];

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m) != EOF)

    {

        for(int i = 1; i <= n; i++)

            for(int j = 1; j <= m; j++)

            {

                scanf("%I64d",&a[i][j]);

            }

        a[1][2] *= a[1][1];

        a[2][1] *= a[1][1];

        for(int i = 1; i <= n; i++)

            for(int j = 1; j <= m; j++)

            {

                if((i+j)%2)

                {

                    int t1,t2,t3;

                    t1 = t2 = t3 = inf;

                    if(j > 2)

                        t1 = a[i][j-2]+a[i][j]*a[i][j-1];

                    if(i > 1 && j > 1)

                        t2 = a[i-1][j-1]+min(a[i][j]*a[i-1][j],a[i][j]*a[i][j-1]);

                    if(i > 2)

                        t3 = a[i-2][j]+a[i-1][j]*a[i][j];

                    t1 = min(t1,t2);

                    t1 = min(t1,t3);

                    if(t1 >= inf)

                        continue;

                    a[i][j] = t1;

                }

            }

        printf("%I64d\n",a[n][m]);

    }

    return 0;

}