HDU 2845 Beans (动态调节)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

242

Source

<a target="_blank" href="http://acm.hdu.edu.cn/search.php?field=problem&amp;key=2009%20Multi-University%20Training%20Contest%204%20-%20Host%20by%20HDU&amp;source=1&amp;searchmode=source">2009 Multi-University Training Contest 4 - Host by HDU</a>

Recommend

这道题意思能够转换成：

对每一行，不能有间隔的取一个子序列，即取该行的最大不连续子序列和；

再从上面全部值中，取其最大不连续子序列和；就相当于隔一行取了

状态：f[i]表示取第i个元素(a[i]必取)的最大值，map[i]表示取到a[i]（可不取）时的最大值

状态转移：f[i]=map[i-2]+a[i];map[i]=max{map[i-1],f[i]};

版权声明：本文博主原创文章。博客，未经同意不得转载。

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/4869646.html，如需转载请自行联系原作者