专栏首页小樱的经验随笔POJ 2209 The King(简单贪心)

POJ 2209 The King(简单贪心)

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

3
3
2 -1 1

Sample Output

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代码:

 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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • UVA 11292 Dragon of Loowater(简单贪心)

    Problem C: The Dragon of Loowater Once upon a time, in the Kingdom of Loowater, ...

    Angel_Kitty
  • Codeforces Round #411 (Div. 2)(A,B,C,D 四水题)

    A. Fake NP time limit per test:1 second memory limit per test:256 megabytes inpu...

    Angel_Kitty
  • POJ 1017 Packets

    Packets Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 53812...

    Angel_Kitty
  • 【论文推荐】最新6篇机器翻译相关论文—词性和语义标注任务、变分递归神经机器翻译、文学语料、神经后缀预测、重构模型

    【导读】专知内容组整理了最近六篇机器翻译(Machine Translation)相关文章,为大家进行介绍,欢迎查看! 1. Evaluating Layers...

    WZEARW
  • 结合人类和机器智能,利用社会媒体图像进行快速损伤评估(CS SI)

    快速损失评估是应对组织在灾害发生时执行的核心任务之一,目的是了解道路、桥梁和建筑物等基础设施的损失程度。 这项工作分析了社会媒体图像内容的有用性,以执行快速损害...

    用户7095611
  • 资源 | Facebook开源DrQA的PyTorch实现:基于维基百科的问答系统

    选自GitHub 机器之心编译 参与:Panda 今年 4 月,斯坦福大学和 Facebook 人工智能研究所在 arXiv 发布了一个基于维基百科的开放域问题...

    机器之心
  • 一个有效的许可区块链与可证明的信誉机制(Computers and Society)

    许可区块链,只允许已知节点参与,已广泛应用在政府、公司、研究所等等。我们研究了将许可的区块链应用于横向战略联盟领域的案例,以确保联盟中任何不遵守规则的参与者在事...

    用户6869393
  • 使用深度学习序列预测光伏发电,并注意序列模型(CS)

    (住宅)光伏(PV)电力作为分布式能源的普及率不断提高,给电力基础设施带来了许多挑战。我们迫切需要高质量、通用的工具来提供准确的电力生产预测。在本文中,我们提出...

    孙孙孙
  • How AI is Changing the Future of Web Development?

    How Artificial Intelligence is changing the future of web development? What is t...

    用户4822892
  • 【论文推荐】最新5篇推荐系统相关论文—文档向量矩阵分解、异构网络融合、树结构深度模型、深度强化学习、负二项矩阵分解

    【导读】专知内容组整理了最近五篇推荐系统(Recommender System)相关文章,为大家进行介绍,欢迎查看! 1. ParVecMF: A Paragr...

    WZEARW

扫码关注云+社区

领取腾讯云代金券