HDU 2845 Beans（dp+求两次最达不连续子序列和）

曾经终败给现在 2022-06-12 01:17 131阅读 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_1499482742][]  
  
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

题解：

比赛的时候没想出来，看了博客懂了，由题意就是求两次不连续最大子序列和，横着一次竖着一次，讲解看注释

我看的博客：http://www.2cto.com/kf/201408/323478.html

代码：

#include<iostream>
    #include<stdio.h>
    #include<string>
    #include<cstring>
    #include<map>
    #include<queue>
    #include<stack>
    #include<algorithm>
    #include<math.h>
    #include<deque>
    #include<stack>
    using namespace std;
    int a[20005];//数据保存
    int p1[20005];//i处取
    int p2[20005];//i处不取
    int b[20005];//每一行的情况
    int m,n;
    int dp(int c[],int len)//求不连续最大子序列和
    {
        int i,j;
        p1[0]=0;//初始化一下
        p2[0]=0;
        for(i=1;i<=len;i++)
        {
            p1[i]=p2[i-1]+c[i];//取的时候即为不取的时候+当前值
            p2[i]=max(p1[i-1],p2[i-1]);//不取即前一个取的情况和不取的情况的最大值
        }
        return max(p1[len],p2[len]);//len处取与不取的最大值
    }
    int main()
    {
        int i,j,x;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=m;j++)
                {
                    scanf("%d",&a[j]);
                }
                b[i]=dp(a,m);//存下每一行最大不连续子序列和
            }
            printf("%d\n",dp(b,n));//输出每一列最大不连续子序列和
        }
        return 0;
    }

[61bb4e1bcb6e9444195e4626035a84e4_v_1499482742]: https://odzkskevi.qnssl.com/61bb4e1bcb6e9444195e4626035a84e4?v=1499482742