网站建设的知名品牌,4399小游戏网页在线玩,外链代发排名,小程序登录模板本来是很简单的一道题#xff0c;却想了好长时间 由于数据量比较大#xff0c;所以逐行读入#xff0c;逐行处理 先处理每一行的不相邻元素和的最大值#xff0c;记录在数组b中 最后计算不相邻行的和的最大值 二者的状态转移方程都类似#xff1a;dp[j] max(dp[j - 1], d…本来是很简单的一道题却想了好长时间 由于数据量比较大所以逐行读入逐行处理 先处理每一行的不相邻元素和的最大值记录在数组b中 最后计算不相邻行的和的最大值 二者的状态转移方程都类似dp[j] max(dp[j - 1], dp[j - 2] a[j]); 1 //#define LOCAL2 #include iostream3 #include cstdio4 #include cstring5 #include algorithm6 using namespace std;7 8 const int maxn 200000 5;9 int a[maxn], b[maxn], dp[maxn];
10
11 int main(void)
12 {
13 #ifdef LOCAL
14 freopen(2845in.txt, r, stdin);
15 #endif
16
17 int row, col;
18 while(scanf(%d%d, row, col) 2)
19 {
20 dp[0] 0;
21 for(int i 1; i row; i)
22 {//处理行
23 scanf(%d, a[1]);
24 dp[1] a[1];
25 for(int j 2; j col; j)
26 {
27 scanf(%d, a[j]);
28 dp[j] max(dp[j - 1], dp[j - 2] a[j]);
29 }
30 b[i] dp[col];
31 }
32
33 dp[1] b[1];
34 for(int j 2; j row; j) //处理列
35 dp[j] max(dp[j - 1], dp[j - 2] b[j]);
36
37 printf(%d\n, dp[row]);
38 }
39 return 0;
40 } 代码君 转载于:https://www.cnblogs.com/AOQNRMGYXLMV/p/3871015.html
