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 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
; }