首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >poj 1976 A Mini Locomotive(01背包)

poj 1976 A Mini Locomotive(01背包)

作者头像
xindoo
发布2021-01-22 14:38:22
3340
发布2021-01-22 14:38:22
举报
文章被收录于专栏:XINDOO的专栏XINDOO的专栏

题目链接

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.

题意:题目的大概意思就是说给你n个数,然后就是有三辆货车头可以拉连续k辆车厢,问你这三个火车头最终可以拉的最大的乘客数是多少。

解题思路:本网上说是01背包,起初自己想的时候想不通,主要是那个连续的啦m辆车

不好想。后来看了别人的代码。终于明白了,是01背包。

解题思路是用sum【】这个数组将连续m个车厢的人储存进去。然后开始01背包。其实是将b【i】,01背包。

为什么要用一个4列的数组呢。这是因为第一,第二,第三,分别表示的一辆车,两辆车,三辆车的拉的人。

如何结局开始那个连续车厢的问题呢,这就是本题的特殊之处。用k=i-m来表示

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

这个方程非常重要,意义是如果b【i】不取,则选出前一列,且车数不变的值,如果b【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[50005], sum[50005];
int dp[500005][4];

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][3]);
    }
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2013-04-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档