NOJ——1568走走走走走啊走（超级入门DP）-白红宇

NOJ——1568走走走走走啊走（超级入门DP）

阅读量：5039 次

发布时间：2019-06-12

本文共 976 字，大约阅读时间需要 3 分钟。

[1568] 走走走走走啊走

时间限制: 1000 ms　内存限制: 65535 K

问题描述

菜菜赚了钱回来，想起要买很多桶回来，不同地方的桶质量是不同的，他在（1，1）点出发因为飞机票有点贵所以他只能向我们的所在地（n，m）处移动，也就是只能向右和下移动，

我们有的桶可能吃腻了所以（i，j）点的值可取可不取；但是菜菜自己也会饿所以在某些城市会吃掉一部分，甚至先透支一部分，所以a(i, j)可以为负，

为了犒劳我们他尽可能会多带一点问他最多带多少质量回来

输入

输入n,m (n,m <= 1000)

再输入n行m列值A(i,j) A(i,j)在 - 1000 ~ 1000 之间。而且A（i,j）可以取可以不取.只能往右或者往下走。

问你，从左上角走到右下角，可以得到的最大值是多少。

输出

输出最大值

样例输入

```
3 31 2 34 5 64 8 9
```

样例输出

```
27
```

提示

```
1 -> 4 -> 5 -> 8 -> 9
```

原理跟数塔比较像，四种状态：上面和左边走过来（2） * 取或不取（2）。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 using namespace std;typedef long long LL;#define INF 0x3f3f3f3fint pos[1010][1010];int dp[1010][1010];int main(void){ int n,m,temp,i,j; while (~scanf("%d%d",&n,&m)) { memset(pos,0,sizeof(pos)); memset(dp,0,sizeof(dp)); for (i=0; i