题目：
又是一道，没有思想的题，看了题解，我发现我的dp题几乎都看了题解，我总是想不好状态转移方程，汗颜，以后怎么比赛啊。
先排序，然后说一个数学问题。
首先，要怎么搬呢？即每一对要怎么取？如果有abcd四个数，且a<b<c<d，应该是取ab，cd好呢还是ac，bd好？抑或是bc，ad好呢？答案是第一种，因为：
(a-b)^2+(c-d)^2 < (a-c)^2+(b-d)^2(a-b)^2+(c-d)^2 < (a-d)^2+(b-c)^2
即每对物品都应是重量最为接近的物品，也就是说对n件物品排序后，每对物品都应该是连续的。
定义数组w[i]为搬第i对物品所消耗的疲劳值；数组dp[n][k]来表示在n件物品中搬k对的最佳状态，而达到这一状态的决策可能为：
- 第n件物品不搬，即在前n - 1件物品中搬k对，那么疲劳值仍为dp[n - 1][k]；
- 第n件物品要搬，那么根据上面所证，第n - 1件物品也要同时搬，即在前n - 2件物品中搬k - 1对物品，再搬最后一对物品，那么疲劳值为dp[n - 2][k - 1] + w[n - 1]。
为使疲劳值最小，因此最佳策略为取两种决策中的最小值，即应使：
dp[n][k] = min(dp[n - 1][k], dp[n - 2][k - 1] + w[n - 1])
应该注意的是要考虑边界问题，dp[i][j]中：
- 当2 * j > i时，即要搬的数量超过了物品总量，这是不可能发生的，因此此时令dp[i][j]为无穷大；
- 当j == 0时，即在一对物品都没搬时，所需疲劳值应该是0，此时令dp[i][j] = 0。
#include#include #include #include #include #include #define inf 0x3f3f3f3ftypedef long long ll;using namespace std;int n,k,w[2010],dp[2010][1010];int main(){ while(scanf("%d%d",&n,&k)!=EOF) { for(int i=1;i<=n;i++) { scanf("%d",&w[i]); } sort(w+1,w+1+n); for(int i=1;i