我很少寫較長(zhǎng)的題解，但是對(duì)于這一題我覺得很有必要。
對(duì)于這道題，首先應(yīng)該想到貪心：每次取差值最小的一對(duì)。但是這樣的貪心策略很容易找到反例，而且N=5000的數(shù)據(jù)規(guī)模，十分有可能是O(n^2)的算法。
于是考慮動(dòng)態(tài)規(guī)劃。如果是DP，那么很容易想到如下的狀態(tài)定義：d[i][j]表示用前j個(gè)數(shù)組成i個(gè)(x,y,z)數(shù)對(duì)的最小消耗。
另外一個(gè)很容易注意到的地方就是：對(duì)于一個(gè)最優(yōu)決策中的任意一個(gè)數(shù)對(duì)(x,y,z)，其中x和y必在有序的a[i]中相鄰。關(guān)于這點(diǎn)用反證法不難證明，也很容易注意到。
對(duì)于(x,y,z)中的z應(yīng)該如何決策的問題，之前一直令我迷惑，這一點(diǎn)應(yīng)該是題目最難解決的問題。

考慮狀態(tài)d[i][j]:
    對(duì)于x和y，有如下考慮：
        對(duì)于a[j]，如果不使用a[j]，那么d[i][j]=d[i][j-1]；
        如果使用a[j]，那么就和a[j-1]一起使用，d[i][j]=d[i-1][j-2]+w(a[i],a[i-1])；
    于是有了總的狀態(tài)轉(zhuǎn)移方程：d[i][j]=min{d[i][j-1],d[i-1][j-2]+w(a[i],a[i-1])}；
    這應(yīng)該不難理解，但是對(duì)于z的決策呢？
    如果把a(bǔ)[i]按降序排列，那么z的影響就可以忽略了！這樣依然可以采用上面的方程。

考慮狀態(tài)d[i][j]：
    如果j<3i，此時(shí)當(dāng)前策略是不可行的，d[i][j]=INF；
    如果j>=3i，即j>=3(i-1)+3，j>3(i-1)+2，當(dāng)前狀態(tài)有效
        轉(zhuǎn)移到d[i-1][j-2]時(shí)，至少剩余一個(gè)多余的a[k]
        由于序列降序，a[k]可以和a[j]、a[j-1]配對(duì)
        同時(shí)d[i-1][j-2]有效，可以繼續(xù)遞歸。
        轉(zhuǎn)移到d[i][j-1]
        若d[i][j-1]為無效狀態(tài)，d[i][j-1]==INF，必然不會(huì)比上面那種轉(zhuǎn)移方式優(yōu)；
        若d[i][j-1]為有效狀態(tài)，可以繼續(xù)遞歸地進(jìn)行下去。

以下是我的代碼，采用的記憶化搜索：