sicily 1419（動態規劃）

 
解題思路：（一道稍微有點不一樣的動態規劃題目）
剛開始看到題目就立馬想到一種動規的解法，用dp[i][j]表示第 i 個到達第 j 個點，可是這種做法有一個問題——推導下一個點的時候需要用到再上一個點的數據（因為越慢送的牛奶需要花費越多時間），這樣時間復雜度就會達到o( n^3 )，必然超時，於是我們可以看出，要解這道題，要解決兩個問題：
1）首先要搜遍所有的數據可能性；2）可以求得最終的總時間

這兩個問題，想了好久，發現自己傻逼了……
1）為了使總時間最小，那麼只要經過那個點必然就會放下牛奶，所以（假設當前送到了第 i+1 家）第 i 家必然是從第 L 層上來的離 i+1 最近的一家或者另一頭的某一家，這樣的話並沒有n種情況啊，只有L層之下的那些，還有離 i 最近的一個；
2）最終的總時間，因為當前的時間會對後來的時間產生影響，所以（假設從當前點走到下一個點的距離為d，剩余x個點）最後總時間會增加 d*x；（嗯，這樣就夠了）

最終解法：
首先把所有的樓層（包括L）排一下序，然後用dp[i][j]表示區間 i ~ j 的最短時間（第 i 個點到第 j 個點），不過，還不夠，因為終點不同，對後續移動的影響也不同，所以我們需要兩個dp數組來記錄（dp[0]和dp[1]，0代表終點在L下面，1則相反），然後狀態轉移方程為：
dp[0][i][j]=min(dp[0][i+1][j]+(a[i+1]-a[i])(n-j+i) , dp[1][i+1][j]+(a[j]-a[i])(n-j+i));
dp[1][i][j]=min(dp[1][i][j-1]+(a[j]-a[j-1])(n-j+i) , dp[0][i][j-1]+(a[j]-a[i])(n-j+i));
其中，i < index , j > index（index為L的索引）
代碼如下：

#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f

using namespace std;

int n,L,a[1005],dp[2][1005][1005];

int main()
{
    int T,index;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&L);
        for(int i=0;i=0;i--)
        {
            for(int j=index;jindex)
                    dp[1][i][j]=min(dp[1][i][j-1]+(a[j]-a[j-1])*(n-j+i),
                        dp[0][i][j-1]+(a[j]-a[i])*(n-j+i));
            }
        }
        printf("%d\n",min(dp[0][0][n-1],dp[1][0][n-1])); 
    }

    return 0;
}

總結：
1、有點難度的題，重在狀態的考慮；
2、動規還是不夠熟悉，害得多加練習。