AI工具人

# poj 1976 A Mini Locomotive(01背包)

Description

A train has a locomotive that pulls the train with its many passenger coaches. If the locomotive breaks down, there is no way to pull the train. Therefore, the office of railroads decided to distribute three mini locomotives to each station. A mini locomotive
can pull only a few passenger coaches. If a locomotive breaks down, three mini locomotives cannot pull all passenger coaches. So, the office of railroads made a decision as follows:

1. Set the number of maximum passenger coaches a mini locomotive can pull, and a mini locomotive will not pull over the number. The number is same for all three locomotives.

2. With three mini locomotives, let them transport the maximum number of passengers to destination. The office already knew the number of passengers in each passenger coach, and no passengers are allowed to move between coaches.

3. Each mini locomotive pulls consecutive passenger coaches. Right after the locomotive, passenger coaches have numbers starting from 1.

dp[i][j]=max(dp[i-1][j],dp[k][j-1]+sum[i]);

b【k】【j-1】的值，及相差m的行使之不连续，前一列使之表示少取一辆车；

```//poj1976 01背包
//2013-04-12-16.25
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int a, sum;
int dp;

int main()
{
int t, n, m;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for (int i = 1; i <= n; i++)
scanf("%d",&a[i]);
scanf("%d",&m);
memset(sum, 0, sizeof(sum));
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n-m+1; i++)
{
for (int j = i; j < m+i; j++)
{
sum[i] += a[j];
}
}
for (int i = 1; i <= n-m+1; i++)
{
int k;
if (i - m < 0)
k = 0;
else
k = i-m;
for (int j = 1; j <= 3; j++)
{
dp[i][j] = max(dp[i-1][j], dp[k][j-1] + sum[i]);
//因为子段不能相交，所以只能对比前m的状态
}
}
printf("%d\n",dp[n-m+1]);
}
return 0;
}
```

### 觉得文章有用就打赏一下文章作者

#### 支付宝扫一扫打赏 #### 微信扫一扫打赏 