题目描述

给定一个序列$a_1..a_{3n}$，求一个长3k的子序列$a_{p_1}..a_{p_{3k}},1\le p_1<p_2<..<p_{3k}\le 3n$，使$\sum _{i=1..k}medium(a_{p_{3i-2}},a_{p_{3i-1}},a_{p_{3i}})$最大。$medium$ 表示中位数。对k=1..n依次给出答案。

输入格式

第一行1个正整数n

第二行3n个整数$a_1..a_{3n}$

输出格式

一行n个整数，依次表示k=1..n的答案

样例 #1

样例输入 #1

3
1 2 3 1 2 3 1 2 3

样例输出 #1

3 5 6

提示

【输入输出样例1说明】

$k=3$ 时选 $(3,3,3)$

$k=2$ 时选 $(2,3,2,3,2,3)$

$k=$ 3时(只能)选整个原序列

最优方案不一定唯一

【数据规模与约定】

100%的数据，$n≤6$

我的代码（0pts）

#include<bits/stdc++.h>
using namespace std;
long long n,a[20005],p[20005],ans[20005],k,maxn=-1;
void cal()
{
	long long sum=0,c=0,q[20005];
	for(long long i=1;i<=3*n;i++)
		if(p[i])
			q[++c]=a[i];
	for(long long i=1;i<=k;i++) 
	    sum+=min(max(a[q[3*i-2]],a[q[3*i-1]]),a[q[3*i]]);
	maxn=max(maxn,sum);
void dfs(long long x,long long cnt) 
{
    if(x==3*n+1) 
	{
		if(!cnt) cal();
		return;
	}
	if(cnt>0)
	{
    	p[x]=1;
    	cnt--;
    	dfs(x+1,cnt);
    	cnt++;
	}
	p[x]=0;
	dfs(x+1,cnt);
}
int main()
{
	cin>>n;
	for(long long i=1;i<=n*3;i++) cin>>a[i];
	for(k=1;k<=n;k++)
	{
		maxn=-1;
		dfs(1,k*3);
		cout<<maxn<<"    ";
		for(int i=1;i<=3*k;i++) cout<<ans[i]<<" ";
		cout<<endl;
	}
	return 0;
}