#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int data[10050],dp[10050];
int One(int i){return  data[i]+data[0];}
int Two(int i){return max(data[i],data[i+1])+data[0]+2*data[1];}
int main()
{
	int T,n,i,j,ans,tmp;
	cin>>T;
	while(T--&&scanf("%d",&n)){
		for(i=0;i<n;i++) scanf("%d",data+i);
		sort(data,data+n);
		dp[0]=data[0],dp[1]=data[1],dp[2]=data[0]+data[1]+data[2];
		for(i=3;i<n;i++)
			dp[i]=min(dp[i-1]+One(i),dp[i-2]+Two(i-1));
		printf("%d\n",dp[n-1]);
	}
}

• Re:这题不能贪心吧。。。按DIS里的去贪心就过了。是DP。。 (561) zjq106891 2020-03-18 14:46:19
• Re: 和贪心思路有点像 (2) zjq106891 2020-03-18 14:52:00