Beans

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2596 Accepted Submission(s): 1279

Problem Description 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.

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

Source 2009 Multi-University Training Contest 4 - Host by HDU
Recommend gaojie | We have carefully selected several similar problems for you: 2830 2577 2870 1159 1176

这道题意思可以转换成：对每一行，不能有间隔的取一个子序列，即取该行的最大不连续子序列和；再从上面所有值中，取其最大不连续子序列和；就相当于隔一行取了

状态：f[i]表示取第i个元素(a[i]必取)的最大值，map[i]表示取到a[i]（可不取）时的最大值状态转移：f[i]=map[i-2]+a[i];map[i]=max{map[i-1],f[i]};

#include 
  
   
#include 
    
    using namespace std
    ; #define M 200001 
    int vis
    [M
    ],map
    [M
    ],dp
    [M
    ],f
    [M
    ]; int max
    (int a
    [],int n
    ) //求在a[]中最大不连续子序列和。 { int i
    ; f
    [0
    ]=map
    [0
    ]=0
    ; f
    [1
    ]=map
    [1
    ]=a
    [1
    ]; for(i
    =2
    ;i
    <=n
    ;i
    ++) //要保证i-2不会数组越界。 { f
    [i
    ]=map
    [i
    -2
    ]+a
    [i
    ]; //因为要隔一个取，所以取了a[i],就不能取a[i-1],所以最大值就是前i-2个数的最大值+a[i]. map
    [i
    ]=f
    [i
    ]>map
    [i
    -1
    ]?f
    [i
    ]:map
    [i
    -1]; //如果取a[i]要更大，更新map[i]的值。 
     } return map
    [n
    ]; } int main(int i
    ,int j
    ,int k
    ) { int n
    ,m
    ,tot
    ,cur
    ; while(scanf
    ("%d%d"
    ,&n
    ,&m
    )!=EOF
    &&n
    &&m
    ) { for(i
    =1
    ;i
    <=n
    ;i
    ++) { for(j
    =1
    ;j
    <=m
    ;j
    ++) scanf
    ("%d"
    ,&vis
    [j
    ]); dp
    [i
    ]=max
    (vis
    ,m
    ); } printf
    ("%d\n"
    ,max
    (dp
    ,n
    )); } return 0
    ; }

HDU 2845 Beans (动规)

Beans