Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes!

这题不能贪心吧。。。按DIS里的去贪心就过了。是DP。。

Posted by v11 at 2011-02-04 14:30:15 on Problem 1700
#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]);
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator