[luogu1594]护卫队（dp）

1066: [视频]动态规划入门（一维一边推4：护卫队）

时间限制: 1 Sec  内存限制: 128 MB
提交: 1313  解决: 535
[提交] [状态] [讨论版] [命题人:admin]

题目描述

【题意】
    护卫车队在一条单行的街道前排成一队，前面河上是一座单行的桥。因为街道是一条单行道，所以任何车辆都不能超车。桥能承受一个给定的最大承载量。为了控制桥上的交通，桥两边各站一个指挥员。护卫车队被分成几个组，每组中的车辆都能同时通过该桥。当一组车队到达了桥的另一端，该端的指挥员就用电话通知另一端的指挥员，这样下一组车队才能开始通过该桥。每辆车的重量是已知的。任何一组车队的重量之和不能超过桥的最大承重量。被分在同一组的每一辆车都以其最快的速度通过该桥。一组车队通过该桥的时间是用该车队中速度最慢的车通过该桥所需的时间来表示的。问题要求计算出全部护卫车队通过该桥所需的最短时间值。
【输入格式】
    第一行包含三个正整数（用空格隔开），第一个整数表示该桥所能承受的最大载重量（用吨表示）；第二个整数表示该桥的长度（用千米表示）；第三个整数表示该护卫队中车辆的总数（n<1000）。

    接下来的几行中，每行包含两个正整数W和S（用空格隔开），W表示该车的重量（用吨表示，车的重量在int的范围内），S表示该车过桥能达到的最快速度（用千米/小时表示）。车子的重量和速度是按车子排队等候时的顺序给出的。
【输出格式】
    输出一个实数，四舍五入精确到小数点后1位，表示整个护卫车队通过该桥所需的最短时间（用分钟表示）。
【样例输入】
100 5 10
40 25
50 20
50 20
70 10
12 50
9 70
49 30
38 25
27 50
19 70
【样例输出】
75.0
【提示】
    本题要学会解释有没有后效性。

#include<bits/stdc++.h>
using namespace std;
const int N= 1000;
long long we,len,n,w[N],sp[N];
double  f[N],t[N][N],ww[N],tj[N];
int main()
{
  cin>>we>>len>>n;
  for(int i=1;i<=n;i++){
      scanf("%d%d",&w[i],&sp[i]);
    tj[i]=(double)len/sp[i]*60.0;  
    t[i][i]=tj[i];     //不要忘记定义边界！ 
  }
  for(int i=1;i<=n;i++)ww[i]=ww[i-1]+w[i];
  for(int i=1;i<=n-1;i++){
      for(int j=i+1;j<=n;j++){
          t[i][j]=max(t[i][j-1],tj[j]);
      }
  }
  for(int i=1;i<=n;i++){
      f[i]=tj[i]+f[i-1];
      for(int j=i-1;j>=1;j--){
          if(ww[i]-ww[j-1]<=we){
              f[i]=min(f[i],f[j-1]+t[j][i]);
          }else break;
      }
  }
  printf("%.1lf",f[n]);
}