我是我做得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