目的地返回POJ 2336 动态规划(DP) Ferry Loading II

在写这篇文章之前，xxx已写过了几篇关于改目的地返回主题的文章,想要了解的朋友可以去翻一下之前的文章

    标题链接：http://poj.org/problem?id=2336

    分析：想设我们要求的是第i辆车最早达到目的地的时光(dp[i] )，则我们只要找到在它之前的n辆车中能最早达到目的地的那辆(mi)，则它的前一辆是(mi-1)小最时光为dp[mi-1](并返回)，最后一次送mi~i辆车去过,时光会最短．

每日一道理
“上下五千年，龙的看火不灭；古有愚公志，而今从头越…… ”站在新世纪的门槛上，我们的追求就是让祖国灿烂的喜悦飞扬在美好的明天……

    即：dp[i]=max(dp[mi-1],f[i])+t*2 ;

    

#include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int maxn=100000; const int inf=10000000; int dp[maxn];///第i辆车被送到的最早时光 int si[maxn];///第i辆车被送到时已送过的数次 int f[maxn]; int main() {int T; cin>>T;while(T--) {int n,t,m; cin>>n>>t>>m;for(int i=1; i<=m; ++i)cin>>f[i];for(int i=1;i<=m;++i){int min=inf,mj;for(int j=i-1;j>=0&&j>i-n;--j)if(dp[j]<=min)min=dp[j],mj=j;if(mj<=0) mj=1;dp[i]=max(dp[mj-1],f[i])+t*2;si[i]=si[mj-1]+1;}cout<<dp[m]-t<<' '<<si[m]<<endl;}return 0; }

文章结束给大家分享下程序员的一些笑话语录： 《诺基亚投资手机浏览器UCWEB，资金不详或控股》杯具了，好不容易养大的闺女嫁外国。（心疼是你养的吗？中国创业型公司创业初期哪个从国有银行贷到过钱？）

转载于:https://www.cnblogs.com/jiangu66/archive/2013/05/04/3060067.html

总结

以上是生活随笔为你收集整理的目的地返回POJ 2336 动态规划(DP) Ferry Loading II的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。