百练+一维度DP

点击打开链接

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<cstring>
#include<string.h>
#include<math.h>
#include<algorithm>
#define inf 0x3f3f3f3f
#define LL long long
using namespace std;
int main()
{
    int weight, num;
    double len;
    int w[10010]={0},v[10010]={0};
    double dp[10010]={0.0};
    while (cin>>weight>>len>>num) {
        len = len*60;
        if(weight==0&&len==0&&num==0) break;
        for(int i=1;i<=num;i++){
            cin>>w[i]>>v[i];
        }
        dp[0]=0.0;
        for(int i=1;i<=num;i++){
            int maxload= w[i], minspeed= v[i];
            dp[i] =len*1.0 /v[i] +dp[i-1];
            for(int j=i-1;j>=1; j--){
                if(maxload+w[j]>weight) break;
                else{
                    maxload+= w[j];
                    minspeed = min(minspeed, v[j]);
                    dp[i] = min(dp[i], len*1.0/minspeed +dp[j-1]);
                }
            }
        }
        printf("%.1f\n",dp[num]);
    }
    return 0;
}