首页 > 代码库 > HDU 2845 Beans

HDU 2845 Beans

2024-07-14 05:43:09   219人阅读

本来是很简单的一道题，却想了好长时间

由于数据量比较大，所以逐行读入，逐行处理

先处理每一行的不相邻元素和的最大值，记录在数组b中

最后计算不相邻行的和的最大值

 

二者的状态转移方程都类似：dp[j] = max(dp[j - 1], dp[j - 2] + a[j]);

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 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 LOCAL14         freopen("2845in.txt", "r", stdin);15     #endif16 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 }
代码君

 

HDU 2845 Beans


联系
我们