AcWing 1018. 最低通行费
原题链接
简单
作者:
呼和
,
2019-09-14 12:47:40
,
所有人可见
,
阅读 1647
此题数据没有负数,若有负数,需要处理 把所有的数字处理成负无穷即可
/*****************************************
Problem Name :
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 100 + 10;
int a[N][N];
int dp[N][N];
int n;
int main()
{
cin >> n;
for(int i = 1 ; i <= n ; i++)
for(int j = 1 , x; j <= n ; j++)
{
cin >> x;
if(i == 1)
dp[i][j] = dp[i][j-1] + x;
else if(j == 1)
dp[i][j] = dp[i-1][j] + x;
else
dp[i][j] = min(dp[i-1][j] , dp[i][j-1]) + x;
}
cout << dp[n][n] << endl;
}
呼和