题目描述：http://acm.pku.edu.cn/JudgeOnline/problem?id=1716

解题报告：http://blog.sina.com.cn/s/blog_64675f540100jri9.html

代码如下：（bellman超时，改成了spfa）

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n, d[10005], cnt, a, b, mmax, v[10005], que[10000*50];
struct edge{int to, v, next;} e[70000];
void insert(int from, int to, int va)
{
    e[cnt].to = to; e[cnt].v = va;
    e[cnt].next = v[from];//每次都插入到最前面
    v[from] = cnt++;
}
bool vst[10005];
void spfa()
{
    memset(vst, 0, sizeof(vst));
    memset(d, -1, sizeof(d));
    d[mmax + 1] = 0;
    int head = 0, tail = 0;
    que[tail++] = mmax + 1;vst[mmax + 1] = 1;
    while(head != tail)
    {
        int from = que[head], id = v[que[head]];
        vst[from] = 0;
        head++;
        while(id != -1)
        {
            int to = e[id].to;
            if (d[to] == -1 || d[from] + e[id].v < d[to])
            {
                d[to] = d[from] + e[id].v;
                if (!vst[to])
                {
                    vst[to] = 1;
                    que[tail++] = to;
                }
            }
            id = e[id].next;
        }
    }
}
int main()
{
    scanf("%d", &n); cnt = mmax = 0;
    memset(v, -1, sizeof(v));
    for(int i = 0; i < n; i++)
    {
        scanf("%d%d", &a, &b);
        insert(b + 1, a, -2);
        if (a > mmax) mmax = a; if (b + 1 > mmax) mmax = b + 1;
    }
    for(int i = 0; i < mmax; i++) insert(i, i + 1, 1);
    for(int i = 1; i <= mmax; i++) insert(i, i - 1, 0);
    for(int i = 0; i <= mmax; i++) insert(mmax + 1, i, 0);
    spfa();
    printf("%d\n", d[mmax] - d[0]);
    return 0;
}