?
解题思路：（一道稍微有点不一样的动态规划题目）
刚开始看到题目就立马想到一种动规的解法，用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;j
index) 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、动规还是不够熟悉，害得多加练习。