POJ 2355(区间最大值-zkw线段树优化Dp方程）

Language:
Railway tickets
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2379 Accepted: 823
Description
从1号车站Ekaterinburg到n号车站Sverdlovsk有一条铁路。

订票时票价如下
2车站间的距离 -X
价格t
0<X<=L1
C1
L1<X<=L2
C2
L2<X<=L3
C3

由于总总原因，距离超过L3的车票不能定。
现在你打算从s号车站乘铁路到t号车站，求最小费用。
Input
第一行有6个数 L1, L2, L3, C1, C2, C3 (1 <= L1 < L2 < L3 <= 10^9, 1 <= C1 < C2 < C3 <= 10^9)
第二行为车站数N (2 <= N <= 10000)
第三行为s和t，表示起点和终点.
接下来n-1行，表示从第1好车站到第i(1<i<=n)号车站的距离（保证是升序）.
Output
仅一行，为最小费用(<10^9)
Sample Input
3 6 8 20 30 40
7
2 6
3
7
8
13
15
23
Sample Output
70
Source
Ural Collegiate Programming Contest 1999
这题就是Dp
显然F[i]=F[j]+c[k](j<i,a[j]-a[i]<=l[k],1<=k<=3) F[i]表示从起点s到车站i的最小费用。
用显然j单调递增，可用指针向后推（O(n)）
注意判断INF为无解情况，可能超过变成负数，线段树记得开大

[cpp]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<cctype>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (20000+10)
#define INF (2139062143)
int l[4],c[4],n,a[MAXN],st,en;
struct SegMentTree
{
    int t[MAXN*10],n,M;
    SegMentTree(){}
    SegMentTree(int _n):n(_n)
    {
        M=1;while (M-2<n) M<<=1;
        memset(t,127,sizeof(t));
    }
    void update(int x)
    {
        for (x>>=1;x;x>>=1) t[x]=min(t[x<<1],t[(x<<1)^1]);
    }
    void insert(int x,int c)
    {
        x+=M;
        if (t[x]>c)
        {
            t[x]=c;//cout<<endl<<'I'<<x<<' '<<c<<endl;
            update(x);
        }
    }
    int find(int l,int r)
    {
        if (l>r) return INF;
        l=l-1+M;r=r+1+M;
        int ans=INF;
        while (l^r^1)
        {
            if (~l&1) ans=min(ans,t[l+1]);
            if (r&1) ans=min(ans,t[r-1]);
            l>>=1;r>>=1;
        }
        return ans;
    }
}t;
void push(int &j,int L,int i)
{
    while (a[i]-a[j]>L) j++;
}
int main()
{
    scanf("%d%d%d%d%d%d%d",&l[1],&l[2],&l[3],&c[1],&c[2],&c[3],&n);
    t=SegMentTree(n);
    scanf("%d%d",&st,&en);if (st>en) swap(st,en);
    if (st==en) {cout<<"0"<<endl;return 0; }
    a[1]=0;
    for (int i=2;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int j[4]={st,st,st,st};
    t.insert(st,0);
    for (int i=st+1;i<=en;i++)
    {
        int value=INF;
        for (int k=1;k<=3;k++)
        {
            push(j[k],l[k],i);
//          cout<<j[k]<<' ';
            int p=t.find(j[k],i-1);
            if (p<INF) p+=c[k];
            value=min(value,p);
        }         www.zzzyk.com
//      cout<<value<<' '<<endl;
        t.insert(i,value);
//      for (int i=1;i<=t.M*2;i++) if (t.t[i]-INF) cout<<i<<' '<<t.t[i]<<' ';
//      cout<<endl;
    }
    cout<<t.find(en,en)<<endl;
    return 0;
}

补充：软件开发 , C++ ,