JZOI-4560 二维数组最小和

题目描述

给出一个二维m*n矩阵grid，含有非负整数。找出一条路径从最左上角到右下角，使之经过元素之和最小。假定只能向右或向下移动

输入

第一行m, n是三角形的行数和列数（1<=m,n<=1000）。
后面m行，每行n个数字是数字三角形aij（0<=aij<=100）。

输出

一行，输出最小的经过的数字的总样例 输入 5 4 3 5 2 9 8 3 12 8 6 7 2 9 14 18 24 9 2 28 19 15 输出 53
  动态规划，就是走一遍，也可以用记忆化递归剪枝，也是一样的速度

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define ull unsigned long long
#define inf INT_MAX    //默认INT_MAX（2147483647）为最大值
#define uinf INT_MIN
#include 
using namespace std;
void p(register int a){
    if(a==1) putchar('\n');
    if(a==2) putchar(' ');
}
void write(register int x){
    if(x>=10) write(x/10);
    putchar(x%10+'0');
}
void read(register int &s){
    s=0;
    register bool flag=false;
    register char ch=getchar();
    while(!isdigit(ch)){
    if(ch=='-') flag=true;
    ch=getchar();
    }
    while(isdigit(ch)){
    s=s*10+ch-'0';
    ch=getchar();
    }
    if(flag) s*=-1;
}
int dp[1086][1086];
int n, m, a[1086][1086];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            read(a[i][j]);   //快读
    dp[1][1]=a[1][1];    //初值状态即为这一位的数字
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){        //O(nm)算法，双重循环
            if(i==1&&j==1) continue;
            int x=dp[i-1][j], y=dp[i][j-1];
            if(i-1==0)        //如果左边没数，那么这个位置不能走
                x=inf;
            if(j-1==0)
                y=inf;    //如果上边没数，那么这个位置不能走
            dp[i][j]=min(x, y)/*走到这一步的最好状态*/+a[i][j];
        }
    }
    cout<