POJ-2336 Ferry Loading II(简单DP)

Ferry Loading II Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 3763 Accepted: 1919 Description

Before bridges were common, ferries were used to transport cars across rivers. River ferries, unlike their larger cousins, run on a guide line and are powered by the river’s current. Cars drive onto the ferry from one end, the ferry crosses the river, and the cars exit from the other end of the ferry. There is a ferry across the river that can take n cars across the river in t minutes and return in t minutes. m cars arrive at the ferry terminal by a given schedule. What is the earliest time that all the cars can be transported across the river? What is the minimum number of trips that the operator must make to deliver all cars by that time? Input

The first line of input contains c, the number of test cases. Each test case begins with n, t, m. m lines follow, each giving the arrival time for a car (in minutes since the beginning of the day). The operator can run the ferry whenever he or she wishes, but can take only the cars that have arrived up to that time. Output

For each test case, output a single line with two integers: the time, in minutes since the beginning of the day, when the last car is delivered to the other side of the river, and the minimum number of trips made by the ferry to carry the cars within that time.

You may assume that 0 < n, t, m < 1440. The arrival times for each test case are in non-decreasing order. Sample Input

2 2 10 10 0 10 20 30 40 50 60 70 80 90 2 10 3 10 30 40 Sample Output

100 5 50 2

其实如果想到状态转移方程还是比较简单的,但是dp题目难的就是状态转移方程啊。我想了挺长时间,还是看了别人的博客。但是这道题目让我对dp题目又有了深刻的认识。我之前之所以想不出来是因为,我把状态弄混了,dp[i]表示第i辆车运送到对岸所花的时间,这个是 车的状态,而不是船的状态。所以所有的思考都应当围绕车子。这辆车被送到对岸,只有两种情况,要么是它不用等,船等着它,它一到就被带走。要么它等着穿,船一来它就跟船走。这就是车子的状态。

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>

using namespace std;
#define MAX 1<<30
int dp[2000];
int bp[2000];
int a[2000];
int n,t,m;
int main()
{
    int c;
    scanf("%d",&c);
    while(c--)
    {
        scanf("%d%d%d",&n,&t,&m);
        for(int i=1;i<=m;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=m;i++)
            dp[i]=bp[i]=MAX;
        dp[0]=-t;
        dp[1]=a[1]+t;
        bp[1]=1;
        for(int i=2;i<=m;i++)
        {
            for(int j=max(0,i-n);j<i;j++)
            {
                dp[i]=min(dp[i],max(dp[j]+t,a[i])+t);
                bp[i]=min(bp[i],bp[j]+1);
            }
        }
        printf("%d %d\n",dp[m],bp[m]);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据科学学习手札

(数据科学学习手札23)决策树分类原理详解&Python与R实现

  作为机器学习中可解释性非常好的一种算法,决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的...

56370
来自专栏数据科学学习手札

【Python让生活更美好01】os与shutil模块的常用方法总结

Python作为一种解释型的高级语言,脚本语言,又被称作“胶水语言”,就是因为其灵活的语法和其依靠浩如烟海的第三方包实现的丰富多彩的功能,而os和shutil就...

372100
来自专栏数据科学学习手札

(数据科学学习手札20)主成分分析原理推导&Python自编函数实现

主成分分析(principal component analysis,简称PCA)是一种经典且简单的机器学习算法,其主要目的是用较少的变量去解释原来资料中的大部...

46670
来自专栏数据科学学习手札

(数据科学学习手札17)线性判别分析的原理简介&Python与R实现

之前数篇博客我们比较了几种具有代表性的聚类算法,但现实工作中,最多的问题是分类与定性预测,即通过基于已标注类型的数据的各显著特征值,通过大量样本训练出的模型,来...

1K100
来自专栏数据科学学习手札

(数据科学学习手札27)sklearn数据集分割方法汇总

一、简介   在现实的机器学习任务中,我们往往是利用搜集到的尽可能多的样本集来输入算法进行训练,以尽可能高的精度为目标,但这里便出现一个问题,一是很多情况下我们...

98770
来自专栏数据科学学习手札

(数据科学学习手札21)sklearn.datasets常用功能详解

作为Python中经典的机器学习模块,sklearn围绕着机器学习提供了很多可直接调用的机器学习算法以及很多经典的数据集,本文就对sklearn中专门用来得到已...

42590
来自专栏数据科学学习手札

(数据科学学习手札22)主成分分析法在Python与R中的基本功能实现

上一篇中我们详细介绍推导了主成分分析法的原理,并基于Python通过自编函数实现了挑选主成分的过程,而在Python与R中都有比较成熟的主成分分析函数,本篇我们...

499100
来自专栏数据科学学习手札

(数据科学学习手札19)R中基本统计分析技巧总结

在获取数据,并且完成数据的清洗之后,首要的事就是对整个数据集进行探索性的研究,这个过程中会利用到各种描述性统计量和推断性统计量来初探变量间和变量内部的基本关系,...

392100
来自专栏数据科学学习手札

(数据科学学习手札25)sklearn中的特征选择相关功能

一、简介   在现实的机器学习任务中,自变量往往数量众多,且类型可能由连续型(continuou)和离散型(discrete)混杂组成,因此出于节约计算成本、精...

54390
来自专栏数据科学学习手札

(数据科学学习手札18)二次判别分析的原理简介&Python与R实现

上一篇我们介绍了Fisher线性判别分析的原理及实现,而在判别分析中还有一个很重要的分支叫做二次判别,本文就对二次判别进行介绍: 二次判别属于距离判别法中的内容...

44590

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励