This post is written in Chinese. Please consider using Google Translate

我是我做得POI的第一道题，应该也是最简单的一道题了。简单的动态规划问题，两问是类似的，仅仅优先选择的条件不同。

我仅说下第一问，状态设定 F[i]到地i个旅店时住宿的最小费用 G[i]到地i个旅店时住宿的最小过夜次数

状态转移方程 F[i]=Min{ F[j] | S[i]-S[j]<=800 } + Cost[i] G[i]=Min{ G[j] | { F[j] | S[i]-S[j]<=800 }} + 1

边界条件 F[0]=G[0]=0

目标解 F[N+1] G[N+1]

#include <iostream>

const int MAX=1002;
const int DIST=800;
const int INF=0x7FFFFFFF;

using namespace std;

int N,T,A;
int S[MAX],F[MAX],G[MAX],C[MAX],H[MAX],Ans[MAX];

void init()
{
    int i;
    freopen("tan.in","r",stdin);
    freopen("tan.out","w",stdout);
    scanf("%d%d",&T,&N);
    for (i=1;i<=N;i++)
    {
        scanf("%d%d",&S[i],&C[i]);
    }
    S[0]=C[0]=C[N+1]=0;
    S[N+1]=T;
}

void dynamic1()
{
    int i,j;
    F[0]=G[0]=0;
    for (i=1;i<=N+1;i++)
    {
        F[i]=G[i]=INF;
        H[i]=0;
    }
    for (i=1;i<=N+1;i++)
    {
        for (j=i-1;j>=0 && S[i]-S[j]<=DIST;j--)
        {
            if (F[j]+C[i]<F[i])
            {
                F[i]=F[j]+C[i];
                G[i]=G[j]+1;
                H[i]=j;
            }
            else if (F[j]+C[i]==F[i] && G[j]+1<G[i])
            {
                G[i]=G[j]+1;
                H[i]=j;
            }
        }
    }
    A=0;
    for (i=N+1;H[i];i=H[i])
    {
        Ans[++A]=H[i];
    }
    for (i=A;i>=2;i--)
    {
        printf("%d ",S[Ans[i]]);
    }
    printf("%dn",S[Ans[1]]);
}

void dynamic2()
{
    int i,j;
    F[0]=G[0]=0;
    for (i=1;i<=N+1;i++)
    {
        F[i]=G[i]=INF;
        H[i]=0;
    }
    for (i=1;i<=N+1;i++)
    {
        for (j=i-1;j>=0 && S[i]-S[j]<=DIST;j--)
        {
            if (G[j]+1<G[i])
            {
                F[i]=F[j]+C[i];
                G[i]=G[j]+1;
                H[i]=j;

            }
            else if (G[j]+1==G[i] && F[j]+C[i]<F[i])
            {
                F[i]=F[j]+C[i];
                H[i]=j;
            }
        }
    }
    A=0;
    for (i=N+1;H[i];i=H[i])
    {
        Ans[++A]=H[i];
    }
    for (i=A;i>=2;i--)
    {
        printf("%d ",S[Ans[i]]);
    }
    printf("%d",S[Ans[1]]);
}

int main()
{
    init();
    dynamic1();
    dynamic2();
    return 0;
}

最优旅行计划
某教练想做一次旅行，将走高速公路，因为在路旁有一些价格实惠的旅馆，这样能沿途花费尽可能的少，不考虑开始点和到达点。为了安全起见，他每天只在白天行走，晚上在旅馆住宿，并且一天的路程不超过800公里。旅行社根据调查，给出了沿路旅馆的相关信息，包括每个旅馆离出发点的距离和该旅馆的价格，当然，为了整个旅行的顺利完成，任意两个旅馆之间的距离都将在800公里以内。 
你的任务是编写一个程序，在旅行距离内，对给定的输入数据，求出，
1）1）费用最少的旅行计划（即中途住宿的费用之和），如果有多个最小费用计划，则取日程最短的计划。
2）2）日程最短的旅行计划（中途在旅馆住宿的天数），如果有多个最短日程计划，则取费用最少的计划。
输入
在文本文件TAN.IN 中的第一行有用一个空格分隔的两个正整数，第一个整数d 表示旅行的距离（单位：公里）。第二个整数 h表示沿途旅社的数目, d <= 16000, h <= 1000。接下来的h行，每行有两个用单个空格分隔的正整数，说明某旅社的相关信息，第一个正整数表示离起点的距离（单位：公里），第二个正整数表示该旅社的价格。价格不会超过1000。 
输出
在文本文件TAN.OUT的第一行输出费用最少的旅行计划；第二行输出日程最短的旅行计划；旅行计划由在所有住宿的旅社组成，对每个旅社，只输出离出发点的距离即可，相邻两个数之间用一个空格分隔。
输入示例
2000 7
100 54
120 70
400 17
700 38
1000 25
1200 18
1440 40
输出示例
400 1200
400 1200