算法：poj 1976 A Mini Locomotive （dp 二维01背包）

算法：poj 1976 A Mini Locomotive （dp 二维01背包）2014-01-10 csdn shuangde800题目大意：

某个车站有N个火车车厢，编号为1～N，每个车厢上有xi个人。

这个车站还有三个火车头，他们能拉最多m个车厢（m<=N/3），而且这m个车厢的编号要连续的。问这三个火车头最多能拉多少个人。

思路：

因为m<=N/3，所以按照贪心的思想，为了拉更多的人，每个火车头一定是要拉m个连续的车厢。

然后，为了求某段连续的车厢共有多少人，可以前缀和预处理，某一段和=sum[ i ] - sum[ i-m].

f[i][j] 代表前i个车厢，用j个火车头拉，最多能拉多少人。

对于第i个车厢，如果当前这个车头选择要拉这个车厢，那么要把以i为最后一个车厢的连续m个车厢一起拉，所以状态转移方程是：

f[i][j] = max（f[i-1][j], f[i-m][j-1]+sum[i]-sum[i- m]）;

代码：

#include<iostream>#include<queue>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include<string>#define MP make_pair#define SQ（x） （（x）*（x））using namespace std;typedef long long int64;const double PI = acos（-1.0）;const int MAXN = 50010;const int INF = 0x3f3f3f3f;int n, m;int w[MAXN], sum[MAXN];int f[MAXN][4];int main（）{int nCase;scanf（"%d", &nCase）;while（nCase--）{scanf（"%d", &n）;for（int i=1; i<=n; ++i）{scanf（"%d", &w[i]）;sum[i] = sum[i-1] + w[i];}scanf（"%d", &m）;memset（f, 0, sizeof（f））;for（int i=m; i<=n; ++i）{for（int j=3; j>=1; --j）{f[i][j] = max（f[i-1][j], f[i-m][j-1]+sum[i]-sum[i-m]）;}}printf（"%d
", f[n][3]）;}return 0;}