题目描述
一个商人穿过一个N×N的正方形的网格,去参加一个非常重要的商务活动。
他要从网格的左上角进,右下角出。
每穿越中间1个小方格,都要花费1个单位时间。
商人必须在(2N-1)个单位时间穿越出去。
而在经过中间的每个小方格时,都需要缴纳一定的费用。
这个商人期望在规定时间内用最少费用穿越出去。
请问至少需要多少费用?
注意:不能对角穿越各个小方格(即,只能向上下左右四个方向移动且不能离开网格)。
输入格式
第一行是一个整数,表示正方形的宽度N。
后面N行,每行N个不大于100的整数,为网格上每个小方格的费用。
输出格式
输出一个整数,表示至少需要的费用。
数据范围
1≤N≤100
样例
输入样例:
5
1 4 6 8 10
2 5 7 15 17
6 8 9 18 20
10 11 12 19 21
20 23 25 29 33
输出样例:
109
样例解释
样例中,最小值为109=1+2+5+7+9+12+19+21+33。
对于这一道题而言,我觉得最大的困难在于读懂题面,如果把题面读懂的话,那么这道题还是很简单的。
分析题目:
每一个方格都会有一个价值,每经过方格一次的代价是方格的价值,经过方格的次数是2N-1,求出走出该网格的最小的代价。
那么,我们在思考一下,我们可以怎么走? 真的是题目中的上下左右都可以走的吗?
因为,我们是从左上角走到右下角的,所以我们先不考虑其他节约代价的走路方式,找出耗费时间最小的方案。
(1,1)的方格可以只经过一次,其他的均采用最优时间的方案就已经是(n-1)*2,所以,我们采用最优时间方案的计划的最少步数就已经是(2 * n-1),所以我们就不可以考虑其他花里胡哨的优化任务了。
然后,我们就只能按照向右以及向下走的方法找到最小的通行费用,这样子,我们就可以想到数字三角形这种题的模板。
用f[i][j]表示当前在从(1,1)第i行第j列的最小费用;
我们的状态转移方程就是:f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j]。
然后就没有了……:ஐ٩(๑´ᵕ`)۶ஐ:*
code
#include<bits/stdc++.h>
using namespace std;
const int nn=103;
int n, a[nn][nn], f[nn][nn];
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int main()
{
n=read();
memset(f,0x3f3f3f3f,sizeof(f));
f[0][1]=0, f[1][0]=0, f[0][0]=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
a[i][j]=read();
f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j];
}
cout<<f[n][n]<<endl;
return 0;
}
memset是按字节赋值, 写0x3f就可以了
不懂就问,read函数是怎么运作的,没看明白, 能指教一下吗?
f[0][1]=0, f[1][0]=0, f[0][0]=0;
这三句话的作用可以解释一下吗QAQ
快读好评
嘿嘿嘿,谢谢大佬夸奖。( ̄▽ ̄)~*