NEFU 169 步步惊心

Description

马尔泰·若曦是康熙年间镇西大将军马尔泰的小女儿，自幼失母，却深得父亲姐姐宠爱，性格活泼任性。张晓，本是21世纪一都市白领，聪慧谨慎，玲珑剔透。因车祸而灵魂穿越到若曦身上，自此开始了步步惊心的宫庭之旅，并身不由己卷进了九龙夺嫡的风波。在这里，若曦与大清未来的皇帝----雍正皇帝新觉罗·胤禛相遇，并上演了一场爱恨情仇中的生死挣扎。权利与亲情、与爱情；欲望和名利下上演一场场惊天动地，凄凉婉转的、曲折的惊心动魄的历史片段。最后在无奈和挣扎中香消玉损，只留下雍正痛苦的坚持和对大清的责任。

   若曦刚来到北京皇宫时，就对复杂的皇宫所迷惑---屋子太多了。皇宫的屋子是m行n列的方格，进到理想的屋子里会得到奖赏（银子），走到禁闭的屋子要扣月厘（银子），难啊。若曦从左下角（1,1）位置，走到右上角（m,n)位置，通过最短的距离能获得的最多银子是多少啊？

（1,1）是左下角的屋子的坐标。

Input

输入数据有多组，每组第一行有2个数m和n（0 < m,n <=100),代表m行，n列，接下来有m行，每行n个数；这m行里的第1行的n个数代表的是皇宫位置m行的位置；而这m行里的第2行的n个数代表的是皇宫位置m-1行的位置；依次；这m行里的第m行的n个数代表的是皇宫位置第1行的位置；具体见图就明白了！每个屋子能得到或失去银子的值为0~100，得到用正数，失去用负数表示。

Output

输出从(1,1)位置开始，走到右上角(m,n)位置，通过最短的距离若曦能获得的最大银子数（不为了银子，谁穿越啊）！

Sample Input

5 5

1 2 7 1 4

1 -6 -7 -3 -2

-6 20 2 0 4

-2 12 6 24 30

10 12 13 -9 -4

Sample Output

101

Hint

sample_input 中的10是（1,1）位置，而4是（5,5）位置，别错！

要求通过最短的距离即在图中只能往上或往右走!

题目比较简单，唯一需要注意的地方就是不能用memset初始化矩阵，因为存在负数，而且要把起始点的上一个点标为0。

#include <cstdio>

#include <iostream>

using namespace std;

int dp[][];

int main()

{

    int m,n;

    while(cin>>m>>n)

    {

        for(int i=;i<=m+;i++)

        for(int j=;j<=n+;j++)

        dp[i][j]=-;

        dp[m][]=;

        for(int i=;i<=m;i++)

        for(int j=;j<=n;j++)

        cin>>dp[i][j];

        for(int i=m;i>=;i--)

        for(int j=;j<=n;j++)

        dp[i][j]+=max(dp[i+][j],dp[i][j-]);

        printf("%d\n",dp[][n]);

    }

    return ;

}

步步惊心

Problem:169

Time Limit:1000ms

Memory Limit:65536K

Description

马尔泰·若曦是康熙年间镇西大将军马尔泰的小女儿，自幼失母，却深得父亲姐姐宠爱，性格活泼任性。张晓，本是21世纪一都市白领，聪慧谨慎，玲珑剔透。因车祸而灵魂穿越到若曦身上，自此开始了步步惊心的宫庭之旅，并身不由己卷进了九龙夺嫡的风波。在这里，若曦与大清未来的皇帝----雍正皇帝新觉罗·胤禛相遇，并上演了一场爱恨情仇中的生死挣扎。权利与亲情、与爱情；欲望和名利下上演一场场惊天动地，凄凉婉转的、曲折的惊心动魄的历史片段。最后在无奈和挣扎中香消玉损，只留下雍正痛苦的坚持和对大清的责任。

   若曦刚来到北京皇宫时，就对复杂的皇宫所迷惑---屋子太多了。皇宫的屋子是m行n列的方格，进到理想的屋子里会得到奖赏（银子），走到禁闭的屋子要扣月厘（银子），难啊。若曦从左下角（1,1）位置，走到右上角（m,n)位置，通过最短的距离能获得的最多银子是多少啊？

（1,1）是左下角的屋子的坐标。

Input

输入数据有多组，每组第一行有2个数m和n（0 < m,n <=100),代表m行，n列，接下来有m行，每行n个数；这m行里的第1行的n个数代表的是皇宫位置m行的位置；而这m行里的第2行的n个数代表的是皇宫位置m-1行的位置；依次；这m行里的第m行的n个数代表的是皇宫位置第1行的位置；具体见图就明白了！每个屋子能得到或失去银子的值为0~100，得到用正数，失去用负数表示。

Output

输出从(1,1)位置开始，走到右上角(m,n)位置，通过最短的距离若曦能获得的最大银子数（不为了银子，谁穿越啊）！

Sample Input

5 5

1 2 7 1 4

1 -6 -7 -3 -2

-6 20 2 0 4

-2 12 6 24 30

10 12 13 -9 -4

Sample Output

101

Hint

sample_input 中的10是（1,1）位置，而4是（5,5）位置，别错！

要求通过最短的距离即在图中只能往上或往右走!