URAL_1031
dp的方程还是很好写的，但如果用裸的O(N^2)的dp的话应该会超时（不过后来翻解题报告的时候有人说O(N^2)也可以过），于是要优化dp的过程。
既然维数已经是一维了，不妨去着眼优化决策的过程，于是猜想到可能费用随着距离的增加是单调递增的（不过即便不是单调递增的，根据dp的方程我们也依然可以用单调队列进行优化），下面就来证明这一点。
设由x出发到y、z(x<y<z)，花费分别为f[y]、f[z]。假设x->z的最优方案中在y的前面紧邻y的那一站是t（t等于y也可以），于是整体路程就变成了x->t->z，构造x->y的路线为x->t->y（x->y中的x->t的部分和x->z中x->t的部分完全一致）。由于在x->z的路线中t是在y前面紧邻y的那一站，那么由t出发是会越过y到达y后面的某一站的，那么就必然可以由t直接到y，而且票价不会更高。因此由x出发到y所花的钱至少不会比x到z所花的钱多。
这样我们分别用3个指针指向3种票价的决策点，如果指针所指站点和当前站点的距离比规定的要大，那么向后移动指针直到符合要求就可以了（我的程序中有些决策未必是符合要求的，比如有时距离不大于L2也可能购买C3的票价，但这样的决策属于多余的，不会影响最后的结果）。
#include<stdio.h> #include<string.h> #define MAXD 10010 int L[3], C[3], x[MAXD], g[3], A[MAXD], N, S, T; long long f[MAXD]; void init() {int i, j, k;scanf("%d", &N);scanf("%d%d", &S, &T);if(S > T)k = S, S = T, T = k;A[1] = 0;for(i = 2; i <= N; i ++)scanf("%d", &A[i]); } void solve() {int i, j, k;memset(f, 0x3f, sizeof(f));f[S] = 0;g[0] = g[1] = g[2] = S;for(i = S + 1; i <= T; i ++)for(j = 0; j < 3; j ++){while(A[i] - A[g[j]] > L[j])++ g[j];if(g[j] < i && f[g[j]] + C[j] < f[i])f[i] = f[g[j]] + C[j];}printf("%lld\n", f[T]); } int main() {while(scanf("%d%d%d%d%d%d", &L[0], &L[1], &L[2], &C[0], &C[1], &C[2]) == 6){init();solve();}return 0; }