这应该是一道DP题。下面的代码是我见过的最短的代码。拿出来跟大家分享。
#include<iostream>
#include<stdio.h>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
int arrival[1450];
int trip[1450];
int time[1450];
int n,t,m;
int main()
{
int test;
cin>>test;
while(test--)
{
cin>>n>>t>>m;
for(int i=1;i<=m;i++)
scanf("%d",arrival+i);
trip[0]=time[0]=0;
for(int j=1;j<=m;j++)
{
time[j]=max(time[max(j-n,0)],arrival[j])+2*t;
trip[j]=trip[max(j-n,0)]+1;
}
printf("%d %d\n",time[m]-t,trip[m]);
}
return 0;
}
然后是该作者的介绍
题目大意:有一些汽车在左岸,你要用一条小破船把它们拉到右岸去。每个测试点包含多个测试数据。第一行的整数C表示测试数据的数目。接下来每个测试数据的第一行为三个整数N, T, M表示一次可以运送N辆汽车,到达对岸的时间为T,汽车的总数是M。接下来的M行每行有一个整数,表示这辆汽车什么时候会来到左岸。对于每个测试数据,输出两个整数,分别是最少要耗用多少时间(包括你等车的时间,就是从0开始直到最后一辆车到达右岸),以及在这个前提下你最少要运送多少次。只要到右岸去就算作一次。
这个题出在DP专场不太合适……事实上本人用贪心的手段就解决了这个问题。
贪心策略:先运送M % N辆汽车到对岸(就是M除上N的余数),之后每次运N辆汽车,直到运完为止。这里的意思是,只有船上确实有了这么多车才出发,在此之前等着那些车来。对于这个策略的证明各位可以使用数学归纳法,比较简单,这里就不耗费篇幅了。
posted on 2010-08-18 21:18
崔佳星 阅读(1150)
评论(0) 编辑 收藏 引用