Posted on 2010-11-29 13:05
小小菜鸟蛋 阅读(468)
评论(0) 编辑 收藏 引用 所属分类:
某蛋的解题报告
http://acm.hdu.edu.cn/showproblem.php?pid=2845
根据题意可知，要选择某个值，则其上下两行和旁边两个都不能选，即要选某个值，受其上一行有没有选择和左边那个有没有选择的影响（因为下一行和右边的可由这个值有否选择来确定其能否选择）。要两次dp，第一次dp每一行，即如若要选择该行，最大值u[i]是多少；第二次dp整个矩阵，其实也就是把第一次dp出的m行最大值u[]按照第一次的方法dp一下，得出最优解~~
设v[i][0]表示那一行的第 i 个值不选，v[i][1]表示要选，a[i]表示那一行的第 i 个值，则：
v[ i ][ 0 ] = max (v[i-1][0], v[i-1][1]) 【第 i 个值不选，则前一个值可选亦可不选】
v[ i ][ 1 ] = v[i-1][0] + a[ i ] 【第 i 个值要选，则前一个值一定不可选】
同理可得f[i][0]和f[i][1]的转移方程。
注意，因为范围是1 <= n * m <= 200000，所以有可能出现n == 200000或m == 200000的情况（虽然看别人的题解知道，hdu没有这样的数据，但最好还是考虑），但是又没法开a[200000][200000]这么大的数组。。。所以就只开a[200000]，然后读入一行就处理一行，然后把结果保存到u[i]就行了~~
01 #include <cstdio>
02 #include <cstring>
03 #include <algorithm>
04 using namespace std;
05
06 const int N = 200000 + 10;
07
08 //v[i][0]表示那一行的第 i 个值不选，v[i][1]表示要选，a[i]表示那一行的第 i 个值
09 //f[i][0]表示第 i 行不选，f[i][1]表示第 i 行要选，u[i]表示第 i 行能取的最大值
10 int f[N][2], v[N][2], u[N], a[N];
11
12 int init(int b[][2], int c[], int n)
13 {
14 int maxnum = 0;
15 for (int i = 1; i <= n; i++)
16 {
17 b[i][0] = max(b[i-1][0], b[i-1][1]);
18 b[i][1] = b[i-1][0] + c[i];
19 int temp = max(b[i][0], b[i][1]);
20 maxnum = maxnum > temp ? maxnum : temp;
21 }
22 return maxnum;
23 }
24
25 int main()
26 {
27 int n, m;
28 while (scanf("%d%d", &m, &n) != EOF)
29 {
30 memset(f, 0, sizeof(f));
31 memset(v, 0, sizeof(v));
32 for (int i = 1; i <= m; i++)
33 {
34 for (int j = 1; j <= n; j++)
35 scanf("%d", &a[j]);
36 u[i] = init(v, a, n);
37 }
38 printf("%d\n", init(f, u, m));
39 }
40 }