NC14582. LP钱不够
描述
输入描述
第一行包含一个正整数T(T<=10)，表示有T组测试数据。
每组数据第一行包含一个正整数n(3 <= n<=20）。
给定一个n*n矩阵图，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是花费和，返回所有路径中最小的花费和。
无摊位时花费为0，不会有负花费。
输出描述
对于每一组数据，有一行输出，返回最小花费，最后输出无换行。
示例1
输入:
1 5 25 81 51 98 43 19 10 36 81 91 95 38 7 84 40 87 27 72 9 30 33 81 68 21 71
输出:
270
C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 1484K, 提交时间: 2023-03-29 20:08:58
#include<bits/stdc++.h>
using namespace std;
int main(){
int t,a[505][505],n;
cin>>t;
while(t--){
cin>>n;
memset(a,0x3f3f,sizeof(a));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
if(i!=1||j!=1)
a[i][j]+=min(a[i-1][j],a[i][j-1]);
}
}
cout<<a[n][n]<<endl;
}
}