步步惊心 Problem:D
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
using namespace std; const int maxn=102; int main() { int m,n; int dp[maxn][maxn]; int a[maxn][maxn]; while(~scanf(“%d%d”,&m,&n)) { memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a));
for(int i=0;i<m;i++) for(int j=0;j<n;j++) cin>>a[i][j]; dp[m-1][0]=a[m-1][0]; for(int i=m-1;i>=0;i--) { for(int j=0;j<n;j++) { if(i==m-1&&j==0) continue; if(i==m-1) { //printf("%d **",dp[i][j-1]); dp[i][j]=dp[i][j-1]+a[i][j]; continue; } if(j==0) {dp[i][j]=dp[i+1][j]+a[i][j]; continue; } dp[i][j]=max(dp[i+1][j],dp[i][j-1])+a[i][j]; } } cout<<dp[0][n-1]<<endl;} return 0; }
