卡最大值的人都应该%^#%#%^

懵逼的 题目

传送至 Luogu

扯淡的 题解

本来想写ST表…
大失败
后来想n^2求最大值还不是稳稳30min A(flag)?
大失败
后来发现精度有问题 心想改完了怕不是能A(flag)?
大失败
看看讨论发现INF要设成9223372036854775807ll(MAXLL)
终于….
思路挺简单, 见第一行的注释

沙茶的 代码

// f[i] 前i辆车最小的通过时间
// f[i] = min(f[i], f[j] + st[i][j]) (j < i); 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define MAXN (2000 + 5)
#define MAXL (10 + 5)
#define INF (9223372036854775807ll)
#define DD double
#define LL long long
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
struct car
{
    LL weight;
    DD time;
}a[MAXN];
LL n;
LL lgn;
LL bw, bl;
LL fr[MAXN];
DD st[MAXN][MAXN];//max time;
DD f[MAXN];
DD ans;
DD stmax(int, int);
void initst();
void dp();
int main()
{
    scanf("%lld%lld%lld", &bw, &bl, &n);
    LL srspeed;
    fr[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld", &a[i].weight, &srspeed);
        a[i].time = (DD) (bl * 60) / srspeed;
        fr[i] = fr[i - 1] + a[i].weight;
    }
    initst();
    /*for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n ; j++)
        {
            printf("%.2lf ", st[i][j]);
        }
        puts("");
    }*/
    dp();
    printf("%0.1lf", ans);
    return 0;
}
void initst()
{
    a[0].time = 0;
    for (int i = 0; i <= n; i++)
    {
        st[i][i] = a[i].time;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= (n - i); j++)
        {
            st[j][j + i] = max(a[j + i].time, st[j][j + i - 1]);
        }
    }
}
DD stmax(int from, int to)
{
    return st[from][to];
}
void dp()
{
    for (int i = 1; i <= n; i++)
    {
        f[i] = INF;
        for (int j = 0; j < i; j++)
        {
            if (((LL)fr[i] - fr[j]) <= bw)
            {
                f[i] = min(f[i], f[j] + stmax(j + 1, i));
            }
        }
    }
    f[n] *= 10;
    ans = floor(f[n] + 0.5);
    ans /= 10;
}
/*
100 5 10
40 25
50 20
50 20
70 10
12 50
9 70
49 30
38 25
27 50
19 70
*/

By 作业写不完把老师都惹炸毛的 Cansult