HDU 1421 搬寢室(DP)

題意 中文

先把物品重量從小到大排序 d[i][j]表示前i件物品選j對的最小疲勞
若選了第i個物品 那麼和它一對的必是第i-1個物品 注意是前i件
i=j*2時 沒有選擇 d[i][j]=d[i-2][j-1]+(w[i]-w[i-1])^2
i>j*2時 存在第i個選或者不選之分
若選了第i個的話 那麼問題就轉化為在i-2個物品中選j-1個了
若不選第i個的話 問題轉化為在i-1個物品中選j個了

那麼就有轉移方程d[i][j]=min(d[i-1][j],d[i-2][j-1]+(w[i]-w[i-1])^2)

d是初始化為無窮大的 所以i=j*2時 d[i-1][j]是等於無窮大的 所以狀態轉移方程可以統一為

d[i][j]=min(d[i-1][j],d[i-2][j-1]+(w[i]-w[i-1])^2)

#include
#include
#include
using namespace std;
const int N = 2014;
int w[N], d[N][N / 2], n, k;

int main()
{
    while (~scanf ("%d%d", &n, &k))
    {
        for (int i = 1; i <= n; ++i)
            scanf ("%d", &w[i]);
        sort (w + 1, w + n + 1);
        memset (d, 0x7f, sizeof (d));
        for (int i = 0; i <= n; ++i)  d[i][0] = 0;
        
        for (int i = 2; i <= n; ++i)
            for (int j = 1; j * 2 <= i; ++j)
                d[i][j] = min (d[i - 1][j], d[i - 2][j - 1] + (w[i] - w[i - 1]) * (w[i] - w[i - 1]));
                
        printf ("%d\n", d[n][k]);
    }
    return 0;
}

搬寢室

Problem Description 搬寢室是很累的,xhd深有體會.時間追述2006年7月9號,那天xhd迫於無奈要從27號樓搬到3號樓,因為10號要封樓了.看著寢室裡的n件物品,xhd開始發呆,因為n是一個小於2000的整數,實在是太多了,於是xhd決定隨便搬2*k件過去就行了.但還是會很累,因為2*k也不小是一個不大於n的整數.幸運的是xhd根據多年的搬東西的經驗發現每搬一次的疲勞度是和左右手的物品的重量差的平方成正比(這裡補充一句,xhd每次搬兩件東西,左手一件右手一件).例如xhd左手拿重量為3的物品,右手拿重量為6的物品,則他搬完這次的疲勞度為(6-3)^2 = 9.現在可憐的xhd希望知道搬完這2*k件物品後的最佳狀態是怎樣的(也就是最低的疲勞度),請告訴他吧.
Input 每組輸入數據有兩行,第一行有兩個數n,k(2<=2*k<=n<2000).第二行有n個整數分別表示n件物品的重量(重量是一個小於2^15的正整數).
Output 對應每組輸入數據,輸出數據只有一個表示他的最少的疲勞度,每個一行.
Sample Input

2 1
1 3

Sample Output

4