华师一附中OI组

标题: 护卫队 [打印本页]
作者: admin    时间: 2018-6-3 11:42
标题: 护卫队
护卫车队在一条单行的街道前排成一队，前面河上是一座单行的桥。因为街道是一条单行道，所以任何车辆都不能超车。桥能承受一个给定的最大承载量。为了控制桥上的交通，桥两边各站一个指挥员。护卫车队被分成几个组，每组中的车辆都能同时通过该桥。当一组车队到达了桥的另一端，该端的指挥员就用电话通知另一端的指挥员，这样下一组车队才能开始通过该桥。每辆车的重量是已知的。任何一组车队的重量之和不能超过桥的最大承重量。被分在同一组的每一辆车都以其最快的速度通过该桥。一组车队通过该桥的时间是用该车队中速度最慢的车通过该桥所需的时间来表示的。问题要求计算出全部护卫车队通过该桥所需的最短时间值。

输入
输入文件第一行包含三个正整数(用空格隔开)，第一个整数表示该桥所能承受的最大载重量(用吨表示)；第二个整数表示该桥的长度(用千米表示)；第三个整数表示该护卫队中车辆的总数(n<1000)。接下来的几行中，每行包含两个正整数W和S(用空格隔开)，W表示该车的重量(用吨表示)，S表示该车过桥能达到的最快速度(用千米/小时表示)。车子的重量和速度是按车子排队等候时的顺序给出的。

输出
输出文件应该是一个实数，四舍五入精确到小数点后1位，表示整个护卫车队通过该桥所需的最短时间(用分钟表示)。

样例
CONVOY.IN
100 5 10
40 25
50 20
50 20
70 10
12 50
9 70
49 30
38 25
27 50
19 70

CONVOY.OUT
75.0
作者: YTC    时间: 2018-6-3 16:48
#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
using namespace std;
double f[1001];
int n,ww,len;
double w[1001],s[1001];
int main()
{
    freopen("convoy.in","r",stdin);
    freopen("convoy.out","w",stdout);
    cin>>ww>>len>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i]>>s[i];
        s[i]=len/s[i]*60.0;
        w[i]=w[i]+w[i-1];
    }
    for(int i=1;i<=n;i++) f[i]=999999999999999.0;
    f[0]=0.0;
    for(int i=1;i<=n;i++)
    {
        double mx=-9999999999999.0;
        for(int j=i;j>=1;j--)
        {
            if(w[i]-w[j-1]>ww) break;
            mx=max(mx,s[j]);
            f[i]=min(f[i],f[j-1]+mx);
        }
    }
    cout<<fixed<<setprecision(1)<<f[n];
    return 0;
}
作者: 胡雨菲菲    时间: 2018-6-7 13:04
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. typedef long long LL;

  6. const int N = 1010;
  7. const LL INF = 1ll << 62;

  9. using namespace std;

  11. LL L, W, n, w[N], sum[N];
  12. double t[N], v[N], f[N], ST[N][60];

  14. void STinit() {
  15.     for(int j = 1; j <= 59; j++) {
  16.         for(int i = 1; i + (1ll << j) - 1 <= n; i++) {
  17.             ST[i][j] = max(ST[i][j - 1], ST[i + (1ll << (j - 1))][j - 1]);
  18.         }
  19.     }
  20.     return;
  21. }

  23. inline double getmax(int l, int r) {
  24.     int k = 0;
  25.     for(int i = 0; i <= 59 && ((1ll << i) <= (r - l + 1)); i++) {
  26.         k = i;
  27.     }
  28.     return max(ST[l][k], ST[r - (1ll << k) + 1][k]);
  29. }

  31. int main() {
  32.     scanf("%lld%lld%lld", &W, &L, &n);
  33.     for(int i = 1; i <= n; i++) {
  34.         scanf("%lld%lf", &w[i], &v[i]);
  35.         t[i] = ((double)L / v[i]) * 60;
  36.         ST[i][0] = t[i];
  37.         sum[i] = sum[i - 1] + w[i];
  38.     }
  39.     STinit();


  42.     f[1] = t[1];
  43.     for(int i = 2; i <= n; i++) {
  44.         f[i] = (double)(INF);
  45.         for(int j = 1; i - j >= 0 && sum[i] - sum[i - j] <= W; j++) {  ///  i - j  |  i - j + 1
  46.             f[i] = min(f[i], f[i - j] + getmax(i - j + 1, i));
  47.         }
  48.     }

  50.     printf("%.1lf", f[n]);
  51.     return 0;
  52. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2