HDU 2845 Beans

发表于 | 分类于 | 阅读次数:

把二维按行列分解然后dp。

dp[i][0]表示不取第i个能到的最大值

所以dp[i][0] = Max(dp[i-1][0],dp[i-1][1]);

dp[i][1]表示取第i个能到的最大值

_所以dp[i][1] = _dp[i-1][0]+value[i];__

row[i]记录下每一行的最优情况,然后再按照上面的方法进行dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Maxn 200001
#define Max(a,b) ((a)>(b)?(a):(b))
int dp[Maxn][2];
int value[Maxn];
int row[Maxn];
int M,N;
int main()
{
    freopen("Sample Input.txt","r",stdin);
    int i,j,k;
    while (scanf("%d%d",&M,&N)!=EOF)
    {
        dp[0][0] = 0;dp[0][1] = 0;
        for (i = 1; i <= M; i++)
        {
            for (j = 1; j <= N; j++)
            {
                scanf("%d",&value[j]);
                dp[j][0] = Max(dp[j-1][0],dp[j-1][1]);
                dp[j][1] = dp[j-1][0]+value[j];
            }
            row[i] = Max(dp[N][0],dp[N][1]);
        }
        dp[0][0] = 0;dp[0][1] = 0;
        for (i = 1; i <= M; i++)
        {
            dp[i][0] = Max(dp[i-1][0],dp[i-1][1]);
            dp[i][1] = dp[i-1][0]+row[i];
        }
        printf("%d\n",Max(dp[M][1],dp[M][0]));
    }
    getch();
    return 0;
}