HDU 2845(动态规划-最大非连续区间)

ゝ一纸荒年。 2022-06-05 03:55 163阅读 0赞

问题描述:

Bean-eating is an interesting game, everyone owns an M\*N matrix, which is filled with different qualities beans. Meantime, there is only one bean in any 1\*1 grid. Now you want to eat the beans and collect the qualities, but everyone must obey by the following rules: if you eat the bean at the coordinate(x, y), you can’t eat the beans anyway at the coordinates listed (if exiting): (x, y-1), (x, y+1), and the both rows whose abscissas are x-1 and x+1.

![61bb4e1bcb6e9444195e4626035a84e4_v_1510583133][]  
  
Now, how much qualities can you eat and then get ?

Input

There are a few cases. In each case, there are two integer M (row number) and N (column number). The next M lines each contain N integers, representing the qualities of the beans. We can make sure that the quality of bean isn't beyond 1000, and 1<=M\*N<=200000.

Output

For each case, you just output the MAX qualities you can eat and then get.

Sample Input

4 6
    11 0 7 5 13 9
    78 4 81 6 22 4
    1 40 9 34 16 10
    11 22 0 33 39 6

Sample Output

242

题目题意:题目给了我们一个矩阵，每格有一个值，我们要在题目要求情况下（满足俩个要求)，求出最总和。

取了(x,y) 则(x,y-1) (x,y+1)不能取，x-1行和x+1行不能取。

题目分析:我们先处理去每一行可以得到的最大值（求最大非连续区间），然后保存起来，按照行的规则，又是一个最大非连续区间。

dp\[i\]=max(dp\[i-1\]+a\[i\],dp\[i-2\]);

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    using namespace std;
    
    const int maxn=2*1e5+100;
    int clomn[maxn],row[maxn],dp[maxn];
    
    int main()
    {
        int n,m;
        while (scanf("%d%d",&n,&m)!=EOF) {
              memset (dp,0,sizeof (dp));
              for (int i=1;i<=n;i++) {
                  for (int j=1;j<=m;j++) {
                      scanf("%d",&clomn[j]);
                  }
                  dp[1]=clomn[1];
                  for (int j=2;j<=m;j++) {
                     dp[j]=max(dp[j-2]+clomn[j],dp[j-1]);
                  }
                  row[i]=dp[m];
              }
              dp[1]=row[1];
              for (int i=2;i<=n;i++)
                dp[i]=max(dp[i-1],dp[i-2]+row[i]);
              printf("%d\n",dp[n]);
        }
        return 0;
    }

[61bb4e1bcb6e9444195e4626035a84e4_v_1510583133]: https://odzkskevi.qnssl.com/61bb4e1bcb6e9444195e4626035a84e4?v=1510583133