【普及组模拟赛】Note

发布于 2019-04-08  11 次阅读


题目描述

数学课上,D突然想到一件很重要的事情要告诉Z,但是她们分别坐在教室的左前方和右后方,这可怎么办呢?
D决定传纸条!
但是问题又出现了,D要告知Z的是个机密,D不希望有很多人知道。可是由于纸条必须经过其它同学,所以D只好希望知道这个机密的人越少越好。
每个同学都有一个好奇程度k(0≤k≤20),好奇程度越大,偷看纸条的可能性也就越大,D希望传递纸条的路径经过的同学的好奇程度和越小越好。
我们假定每个同学只会将纸条传递给ta后方或者右方的同学。

输入

第1行,两个整数n,m,表示教室有n行m列。(1≤n,m≤100)
第2行到第n+1行,每行m个整数,表示每个同学的好奇程度。
其中D在第1行第1列,Z在第n行第m列,她们的好奇程度都为0。

输出

共1行,1个整数,表示传递路径的好奇程度.

思路

很明显的dp水题,f[i,j]=max(f[i1,j],f[i,j1])

#include 
using namespace std;
int f[1000][1000],a[1000][1000];
int min(int x,int y)
{
    return x
]]>