昨天开始感冒，浑身无力，感觉不爽。今天写了两个，第一个是单调子序列，就不贴了。第二个是这个DP。
题目:http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1094
题目意思是求一个序列，这个序列满足三个一组，并且每组有一个属性m，这个m=min((a-b)^2+(b-c)^2+(a-c)^2)，其中a，b，c为序列中这组数的值。求得的序列是在N个元素的序列中的K组，使得这K组的m值和最小。
解法：DP。考虑到如果abc顺序排列，则m只能取得(a-b)^2或(b-c)^2之一。类似01背包，将每个数当作每个物品，这个物品重量是1。因为决定一组数的m值尽取决于两个元素，因此第三个元素可以在没被选择的数里任意选择。
状态转移：dp[i][j]=min(dp[i-2][j-1]+(a[i]+a[i-1])^2,dp[i-1][j-1])。
这个状态转移的意思是，当考察了a中前i项并且最多组k队时的最小m值。这里实际上是在决定将a[i],a[i-1]加入组队，还是保持不变。因为这里每个人的重量为1，而最大容量相当于2*K因此，一定可以将背包装满。因此可以得到K组人。
代码：点击下载