dp解法

这道题是线性dp，我们该怎么来解答呢？
我们可以考虑dpi为前i辆车最少的通过时间。
那我们该如何写这个转移呢？
考虑dp[i] = dp[j - 1] + time; 前i辆车的最短时间是，前i辆车的最短时间，i ~ j为最后一组，所需要的最短时间（time），加上前j - 1 辆车的最短时间（dp[j - 1]。
其次，对于j来说我们需要逆序排列， 如果不逆序，我们需要重新计算前面车子的最短速度。
然后我门需要判断这一组是否超重。根据题意，我们知道通车是只能按顺序，不能超车，也就是说， 我们可以利用前缀和来判断i~j这一个区间内的车子总重量。可以优化判断流程。
代码如下：

#include <bits/stdc++.h>
using namespace std;
#define V vector
#define all0(x) (x).begin(),(x).end()
#define all1(x) (x).begin()+1,(x).end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
typedef long long LL;
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;
const int N = 1000 + 20;
const int INF = 0x3f3f3f3f;
const LL INFLL =0x3f3f3f3f3f3f3f3f;
int W , d , n;
LL w[N] , v[N];
void so() {
		cin >> W >> d >> n;
		vector<double> dp(n + 10 , INFLL) ; //dp[i] 表示前 i 辆车通过的最短时间， 取LL的最大值，如果取int的最大值，会有一个测试点wa掉。
		vector<LL> s(n + 10);//初始情况：没有车辆时间为 0
		for(int i = 1; i <= n ; i++){
			cin >> w[i] >> v[i];
			s[i] = s[i - 1] + w[i]; //因为车是连续的，我们可以用前缀和优化一下
		}
		dp[0] = 0.0; 
		for(int i = 1 ; i <= n ; i++ ){ //只考虑以i~j为最后一组的车辆最短方案数。
			LL miv = v[i]; // 第i辆车的最小速度。
			for(int j = i ; j >= 1 ; j-- ){   //尝试进行分组，求i~j为一组的最小速度（最后一组）
				if(s[i] - s[j - 1] <= W){ //判断是否超重
					miv = min(miv , v[j]); //当前组别，最小速度
					double time = (double)d / miv; // 当前组别最慢通过时间
					dp[i] = min(dp[i] , dp[j - 1] + time); //取最小时间
				}
				else {break;} //超重直接退出内层循环,因为j越小，重量越大
			}
		}
		cout << fixed << setprecision(1) << dp[n] * 60<< endl;
		
}
int main() {
    IOS
    int tt=1;
  //  cin >> tt;
    while (tt--)
    so();
}