AcWing 1018. 最低通行费

题面：

一个商人穿过一个 $N \times N$ 的正方形的网格，去参加一个非常重要的商务活动。

他要从网格的左上角进，右下角出。

每穿越中间 $1$ 个小方格，都要花费 $1$ 个单位时间。

商人必须在 $(2N−1)$ 个单位时间穿越出去。

而在经过中间的每个小方格时，都需要缴纳一定的费用。

这个商人期望在规定时间内用最少费用穿越出去。

请问至少需要多少费用？

注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。

这个题乍一看，诶？咋四个方向都能走，这咋做。仔细读了读之后发现商人要在 $(2N-1)$ 个单位时间穿越出去。那我们可以想一下，一个 $N \times N$ 的正方形的网格，你怎么走才能在只走 $(2N-1)$ 个方格的情况下从左上角走到右下角呢，这里我们可以求一下从左上角到右下角的曼哈顿距离（$\left|x_2-x_1\right|+\left|y_2-y_1\right|$），我们会发现它的值正好等于 $2N-1$ ，也就是说我们在走的过程中只能向右走或者向下走，因为要是向上或者向左走就相当于是做了无用功，离右下角更远了，所以这样就转化成了一个数字三角形的模型。注意这里是要最小值所以用min，我懒得判断边界了，就把 $\text{a}[0][2]-\text{a}[0][100]$ 和 $\text{a}[2][0]-\text{a}[100][0]$ 赋了一个极大值，这样就不会跑到外面去了，不把 $\text{a}[0][1]$ 和 $\text{a}[1][0]$ 赋极大值是因为 $\text{a}[1][1]$ 是起点，如果它的上左两边都有值的话就会给起点赋一个初始值，相当于还没开始走就花钱了，肯定是不行的，在别的题中也要注意这一点。

两个小点：极大值最小为 $10000$ ，这是因为正方形最大长度为 $100$ ，而且网格里的数最大为 $100$ ，所以能接触到边界的数的最大值为 $100 \times 100 =10000$ ，而这个最大数的上面那个数必定比 $10000$ 小，所以极大值最小为 $10000$。还有这里我直接用的一个数组进行读入和动态规划，原因可看摘花生。

#include <iostream>
using namespace std;
int n;
int a[120][120];
int main()
{
    cin>>n;
    for(int i=2;i<=n;++i){
        a[i][0]=200000;
        a[0][i]=200000;
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            cin>>a[i][j],a[i][j]+=min(a[i-1][j],a[i][j-1]);
    cout<<a[n][n]<<endl;
    return 0;
}

没有楼的楼长