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，如需轉載請自行聯系原作者