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!

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

Posted by zjq106891 at 2020-03-18 14:46:19 on Problem 1700
In Reply To:这题不能贪心吧。。。按DIS里的去贪心就过了。是DP。。 Posted by:v11 at 2011-02-04 14:30:15
> #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