這應(yīng)該是一道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;
}


然后是該作者的介紹

題目大意：有一些汽車在左岸，你要用一條小破船把它們拉到右岸去。每個測試點(diǎn)包含多個測試數(shù)據(jù)。第一行的整數(shù)C表示測試數(shù)據(jù)的數(shù)目。接下來每個測試數(shù)據(jù)的第一行為三個整數(shù)N, T, M表示一次可以運(yùn)送N輛汽車，到達(dá)對岸的時間為T，汽車的總數(shù)是M。接下來的M行每行有一個整數(shù)，表示這輛汽車什么時候會來到左岸。對于每個測試數(shù)據(jù)，輸出兩個整數(shù)，分別是最少要耗用多少時間（包括你等車的時間，就是從0開始直到最后一輛車到達(dá)右岸），以及在這個前提下你最少要運(yùn)送多少次。只要到右岸去就算作一次。

這個題出在DP專場不太合適……事實(shí)上本人用貪心的手段就解決了這個問題。

貪心策略：先運(yùn)送M % N輛汽車到對岸（就是M除上N的余數(shù)），之后每次運(yùn)N輛汽車，直到運(yùn)完為止。這里的意思是，只有船上確實(shí)有了這么多車才出發(fā)，在此之前等著那些車來。對于這個策略的證明各位可以使用數(shù)學(xué)歸納法，比較簡單，這里就不耗費(fèi)篇幅了。