Best Route in a Grid(dp)

￡神魔★判官ぃ 2021-09-15 02:30 233阅读 0赞

### Description ###

Given an n\*n grid with non-negative integers, you start from the upper left corner (1,1) and can only move right or down.

Your task is to find the best route to the lower right corner (n,n) without reaching the grid marked with 0.

The best route is when you multiply all the integers you reach on the route, the number of trailing zeros of the product is minimized.

### Input ###

First line with an integer n.

Then n lines, each line with n integers. The numbers in the grid are <= 1,000,000.

The data guarantee that there is at least one legal route.

### Output ###

One line with an integer indicating the answer.

Sample Input

4
    1 3 0 0
    0 8 2 25
    6 5 0 3
    0 15 7 4

Sample Output

题意大概是一个矩阵，从(1,1)走到右下角，只能向下或向右走，且不能到达值为0的方格，求最优路径，最佳路径是指途经的数的乘积的末尾连续的0最少。

dp自然是不能用末尾0的个数做状态的，那么怎么求最少的0呢？10分解成5和2，所以问题就变成求最少的5或最少的2的路径。

upd:今天有人问我这题，他觉得这解法有点问题，其实可以用反证法证明，假设路径A min2最小（比最小的min5还小！！），假如有比它更少的0路径，则一定存在一条路径min5更小，这与A min2 最小矛盾。

状态转移方程:dp\[i\]\[j\]=min(dp\[i\]\[j\],min(dp\[i\]\[j-1\],dp\[i-1\]\[j\])+w\[i\]\[j\])

初始条件:dp\[1\]\[0\]=0,其他为较大值

#include <bits/stdc++.h>
    using namespace std;
    int ma[1100][1100],w[1100][1100],dp[1100][1100];
    int inf=1e8;
    int main()
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            cin>>ma[i][j];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
             if(!ma[i][j])//不能到达为0的方格
               w[i][j]= inf;
             else
             {
                 int t=ma[i][j];
                 w[i][j]=0;
                 while(t%2==0)
                 {
                     w[i][j]++;
                     t/=2;
                 }
             }
             memset(dp,0x3f3f3f,sizeof dp);
             dp[1][0]=0;
             for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                 dp[i][j]=min(dp[i][j],min(dp[i][j-1],dp[i-1][j])+w[i][j]);//只能向下或向右
                 int ans=dp[n][n];
         for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
             if(!ma[i][j])
               w[i][j]= inf;
             else
             {
                 int t=ma[i][j];
                 w[i][j]=0;
                 while(t%5==0)
                 {
                     w[i][j]++;
                     t/=5;
                 }
             }
             memset(dp,0x3f3f3f,sizeof dp);
             dp[1][0]=0;
             for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                 dp[i][j]=min(dp[i][j],min(dp[i][j-1],dp[i-1][j])+w[i][j]);
                 ans=min(dp[n][n],ans);
                 cout<<ans<<endl;
                 return 0;
    }

题后感想:觉得这种拆分的方法还蛮多地方用的。越来越觉得dp只是一个解题的工具，并不能算一种方法。找到有序的整体(即最优子结构)其实就解了一半，计算的对象要是有序的，要有明显的维度，很多时候一道线性dp题感到棘手，就是感觉题目多了点东西，或者一个对象太大无从下手，如何把多的东西有效的装进一个整体或把一个大的对象拆开往往是解题的突破口。