Description
给出3*n个数xi，要求构造三个长度为n的序列ai，bi，ci，使得满足下列条件：
1到3*n的每个数都在三个序列中的某个出现一次且仅一次；
S=sum((x[ai]-x[bi])*x[ci])最大。
输出最大的S。多组数据。
Input Format
第一行包含两个数T和n，T是数据组数，n如题目描述。
接下来T行，每行包含3*n个数，表示xi。
Output Format
输出包含T行，每行输出最大的S。
Sample Input
1 2
4 1 8 2 0 5
Sample Output
46
Hint
对于1<=n<=10，有不超过1000组数据；
对于11<=n<=15，又不超过100组数据；
对于16<=n<=20，有不超过10组数据；
对于21<=n<=25，仅有1组数据。
所有xi<=1000。
Solution
首先先Orz yff，怎么想到dfs的。。。标解是状压DP，还是卡时过的，不知比暴力慢到哪里去了。
1. 当a>=c>=b时(a-b)*c的值最大。推一推就出来了。
2. 将读入的3*n个数从小到大排序，x1~xn一定分别在每组中,且一定是每组的b
3. 将n个三元组(ai,bi,ci)按照ci从小到大排序。为了使Σ( a[i] - b[i] ) * c[i]最大化，根据排序不等式可以得a1<=a2<=a3<=…<=an，b1>=b2>=…>=bn。所以b1=xn，b2=xn-1…bn=x1。
4. 最优性剪枝：两个三元组（ai,bi,ci）与（aj,bj,cj）为最终答案，当且仅当
(ai - bi) * ci + (aj - bj) * cj > (ai - bi) * aj + (ci - bj) * cj
即(ci - aj) (ai - bi - cj) > 0
然后就dfs吧= =
#include<cstdio>
#include<cstring>
#include<algorithm>
int T,n,a[],c[],t[],ans,now;bool vis[];
bool check(int x)
{
for(int i=;i<x;i++)
{
if(c[i]>a[x]&&a[i]-t[*n-i+]<c[x])return ;
if(c[i]<a[x]&&a[i]-t[*n-i+]>c[x])return ;
}
return ;
}
void dfs(int xa,int tc)
{
if(xa==n+)
{
if(ans<now)ans=now;
return;
}
for(int i=xa;i<=*n;i++)
if(!vis[i])
{
vis[i]=,a[xa]=t[i];
for(int j=std::max(i,tc)+;j<=*n;j++)
if(!vis[j])
{
vis[j]=,c[xa]=t[j],
now+=(a[xa]-t[*n-xa+])*c[xa];
if(now*n>ans*xa&&check(xa))dfs(xa+,j);
now-=(a[xa]-t[*n-xa+])*c[xa],vis[j]=;
}
vis[i]=;break;
}
}
bool cmp(int i,int j){return i>j;}
int main()
{
for(scanf("%d%d",&T,&n);T;T--)
{
for(int i=;i<=*n;i++)scanf("%d",&t[i]);
std::sort(t+,t++*n,cmp);ans=;
dfs(,);printf("%d\n",ans);
}
}