本文共 797 字，大约阅读时间需要 2 分钟。

问题：HDU 2845 BeansTime Limit: 140MSMemory: 248KAccepted Time: 2009-08-03 20:57:11Tip: DP

#include <stdio.h>

#define maxs(a,b) (a > b ? a : b)

int main() {int dp[2], dp2[2];int m, n, t;while (scanf("%d%d", &m, &n) != EOF) {int i, j, temp;dp2[0] = dp2[1] = 0;for (i = 1; i <= m; i++) {dp[0] = dp[1] = 0;for (j = 1; j <= n; j++) {scanf("%d", &temp);t = dp[0];dp[0] = maxs(dp[0], dp[1]);dp[1] = t + temp;}t = dp2[0];dp2[0] = maxs(dp2[0], dp2[1]);dp2[1] = t + maxs(dp[0], dp[1]);}printf("%d\n", maxs(dp2[0], dp2[1]));}return 0;}

这段代码是解决HDO 2845 "Beans"问题的C语言程序。程序主要通过动态规划（DP）方法来计算最优解。程序的主要逻辑是：1. 定义两个数组dp和dp2，用于存储当前和上一状态的DP结果。2. 读取输入数据，程序会持续处理直到输入结束。3. 对于每一组输入数据，初始化当前状态dp的两个变量。4. 使用双重循环遍历所有可能的状态，更新dp数组中的最大值和累加和。5. 在每次循环结束时，更新dp2数组，记录当前状态的最大值和累加和。6. 最后输出最终的结果。这个程序的时间复杂度是O(m*n)，空间复杂度是O(1)，适用于处理较大的输入规模。

转载地址：http://tmisz.baihongyu.com/