這應(yīng)該是一道DP題。下面的代碼是我見(jiàn)過(guò)的最短的代碼。拿出來(lái)跟大家分享。
#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;
}


然后是該作者的介紹

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

這個(gè)題出在DP專(zhuān)場(chǎng)不太合適……事實(shí)上本人用貪心的手段就解決了這個(gè)問(wèn)題。

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