Codeforces Round #277.5 (Div. 2), problem: (E) Hiking

類似最優比率樹

二分搜+dp

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define EPS 0.000000001
#define INF 1000000000
using namespace std;
double val[1011];
int from[1011];
int x[1011], b[1011];
int main()
{
    int n, ll; scanf("%d %d", &n, &ll);
    double l = (double)ll;
    x[0] = 0, b[0] = 0;
    for(int lx = 1;lx <= n;lx++)
        scanf("%d %d", x+lx, b+lx);
    val[0] = 0;
    double fmin = 0, fmax = x[n];
    while(fmax - fmin > EPS){
//        printf("%f\n", fmax);
        double ftest = (fmax+fmin)/2;
        for(int lx = 1;lx <= n;lx++){
            val[lx] = INF;
            for(int ly = 0;ly < lx;ly++)
                val[lx] = min(val[lx], 
                sqrt(fabs((double)(x[lx]-x[ly]-ll)))-ftest*(double)(b[lx]) + val[ly]);
        }
        if(val[n] > 0)
            fmin = ftest;
        else
            fmax = ftest;
    }
    from[0] = -1;
    for(int lx = 1;lx <= n;lx++){
        val[lx] = INF;
        for(int ly = 0;ly < lx;ly++){
            double cal = sqrt(fabs((double)(x[lx]-x[ly]-ll)))-fmin*(double)(b[lx]) + val[ly];
            if(val[lx] > cal)
                from[lx] = ly, val[lx] = cal;
        }
    }
    int path[1011], pathcnt = 0;
    int prc = n;
    while(prc != 0){
        //printf("prc = %d\n", prc);
        path[pathcnt++] = prc;
        prc = from[prc];
    }
    for(int lx = pathcnt-1;lx >= 0;lx--)
        printf("%d ", path[lx]);
    printf("\n");
    return 0;
}