前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >POJ 2209 The King(简单贪心)

POJ 2209 The King(简单贪心)

作者头像
Angel_Kitty
发布2018-04-08 15:28:49
6040
发布2018-04-08 15:28:49
举报
文章被收录于专栏:小樱的经验随笔

The King

Time Limit: 2000MS

Memory Limit: 65536K

Total Submissions: 7499

Accepted: 4060

Description

Once upon a time in a country far away lived a king and he had a big kingdom. He was a very clever king but he had one weakness -- he could count only up to three. Nevertheless, he did not consider this to be a really great drawback, since he had a lot of wizards who could count up to one hundred (and some of them, people said, even up to one thousand), so it was all right. But one day the grief came to the kingdom as the outnumbering barbarians started to approach from all sides. And the king then had to make the most important decision in his life. He had to choose which of his sons to make generals that he would send to the borders of the country to lead the army. However, the king knew that though some of his sons were clever, just like he was, some of them were quite stupid and could only lower army spirits with their wrong decisions. More precisely, he knew about each of his sons his mental potential -- an integer number ranging from minus three to three (remember, that the king could count only up to three). He also knew that the chance of his army defeating barbarians was proportional to the sum of some powers of mental potentials of those of his sons that he would make generals (the power exponent was a positive integer number, the same for all his sons and not exceeding three either). Thus he had to choose such a combination of his sons to lead the army, that this sum would be maximal possible. However, the king himself could not make all apropriate calculations since, for example, the second power of the number not exceeding three (which is its square) could be greater than three, and therefore he asked you, his most intellegent wizard, to solve this problem.

Input

The first line of the input file contains the number of the sons of the king (integer number less or equal to one hundred). The second line contains the positive integer number not exceeding three, the exponent in the formula used to calculate the chance of defeating barbarians. The third line contains the list of mental potentials of king’s sons -- all integer numbers, not greater than three by their absolute value.

Output

Output the only number -- the maximal possible chance of defeating barbarians measured as the sum described.

Sample Input

代码语言:javascript
复制
3
3
2 -1 1

Sample Output

代码语言:javascript
复制
9

Hint

In the example above the king should choose his first and third sons to be the generals. In this case the chance to defeat barbarians, which is the sum of cubes of mental potentials of these sons, is eight plus one, that is nine.

Source

Northeastern Europe 2002, Northern Subregion

题目链接:http://poj.org/problem?id=2209

题解:以前挂的一些贪心的题没有做,有位大佬叫我写下题解,有些看不懂题意,我恭敬不如从命了,写点吧,算是复习下贪心吧!

题意:比较难理解,第一个数是数列的长度,第二个数字是指数,第三行是数列,即真数。从数列中选择任意多个,使得他们每个求幂再求和最大。

下面给出AC代码:

代码语言:javascript
复制
 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 using namespace std;
 6 int main()
 7 {
 8     int n,m;
 9     int a[110];
10     int b[110];
11     while(scanf("%d",&n)!=EOF)
12     {
13         scanf("%d",&m);
14         for(int i=0;i<n;i++)
15             scanf("%d",&a[i]);
16         sort(a,a+n);
17         int sum=1,ans=0;
18         for(int i=0;i<n;i++)
19         {
20             for(int j=1;j<=m;j++)
21                 sum*=a[i];
22             if(sum>0)
23                 ans+=sum;
24             sum=1;
25         }
26         printf("%d\n",ans);
27     }
28     return 0;
29 }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-03-20 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档