锐客网

  1. 首页 > it技术 > >

ZOJ-3447---Doraemon's Number Game (贪心+大数）

贪心

Doraemon's Number Game Time Limit: 2 Seconds Memory Limit: 65536 KB Doraemon and Nobita are playing a number game. First, Doraemon will give Nobita N positive numbers. Then Nobita can deal with these numbers for two rounds. Every time Nobita can delete i (2 ≤ i ≤ K) numbers from the number set. Assume that the numbers deleted is a[ 1 ], a[ 2 ] ... a[ i ]. There should be a new number X = ( a[ 1 ] * a[ 2 ] * ... * a[ i ] + 1 ) to be inserted back into the number set. The operation will be applied to the number set over and over until there remains only one number in the set. The number is the result of round. Assume two results A and B are produced after two rounds. Nobita can get |A - B| scores.
Now Nobita wants to get the highest score. Please help him.
Input Input will contain no more than 10 cases. The first line of each case contains two positive integers N and K (1 ≤ N ≤ 100, 1 ≤ K ≤ 50). The following line contains N positive integers no larger than 50, indicating the numbers given by Doraemon.
Output For each case, you should output highest score in one line.
Sample Input

6 3 1 3 4 10 7 15

Sample Output
5563

Hint For most cases, N ≤ 20


题意：给出n和k，有n个数字，从中选择2~k删掉，然后将删掉的数的乘积加1加进去，求算得的最大值与最小值的差；
【ZOJ-3447---Doraemon's Number Game (贪心+大数）】思路：很明显的贪心，求得最大值的策略是每次选取其中最小的两个数求积，求的最小值的策略是每次取出前1~k大的值求积，这题会爆long long，所以要用大数；
样例解释：
求最大值1,3,4,7,10,15 ---（1*3+1）---->4,4,7,10,15---(4*4+1)---->7,10,,15,17---(7*10+1)---->15,17,71---(15*17+1)---->71,256---(71*25+1)---->18177;
求最小值1,3,4,7,10,15---(7*10*15+1)---->1,3,4,1051---(3*4*1051+1)---->1,12613----(1*12613+1)----->12614;
ans=18177-12614=5563;

AC代码：（这个大数模板挺好的，可以带走~）

#include #include #include #include #include #include using namespace std; struct cmp1 { bool operator ()(string a,string b) { if(a.size()==b.size()) return ab; else { return a.size()>b.size(); } } }; priority_queue,cmp1>que1; //优先取出最大元素（优先队列不懂的请另查资料）priority_queue,cmp2>que2; //优先取出最小元素string ans; //********大数加法********// string sum(string s1,string s2) { if(s1.length()=0; i--,j--) { s1[i]=char(s1[i]+(j>=0?s2[j]-'0':0)); //注意细节 if(s1[i]-'0'>=10) { s1[i]=char((s1[i]-'0')%10+'0'); if(i) s1[i-1]++; else s1='1'+s1; } } return s1; }//*******大数乘法**********// string Mult(string s,int x)//大数乘以整形数 { reverse(s.begin(),s.end()); int cmp=0; for(int i=0; i=0; i--,j++) { string tmp=Mult(x,y[i]-'0'); for(int k=0; k=0; i--) { if(a[i]>ss; que1.push(ss); que2.push(ss); } int ans1,ans2; while(que1.size()>1)//求最小值 { string _sum="1"; for(int i=1; i<=k&&que1.size(); i++)//注意队列为空就不能再取了 { _sum=Multfa(_sum,que1.top()); que1.pop(); } string a="1"; _sum=sum(_sum,a); que1.push(_sum); } while(que2.size()>1)//求最大值 { string a=que2.top(); que2.pop(); string b=que2.top(); que2.pop(); string c=Multfa(a,b); a="1"; c=sum(c,a); que2.push(c); } cout<





    推荐阅读


    上一篇：阿里云docker开发者平台镜像上传和下载

    下一篇：JVM|JVM优化（一）