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

考慮狀態(tài)d[i][j]:
    對于x和y，有如下考慮：
        對于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])}；
    這應該不難理解，但是對于z的決策呢？
    如果把a[i]按降序排列，那么z的影響就可以忽略了！這樣依然可以采用上面的方程。

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

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