美丽的牛家庄受到了外星人的侵略, 勇敢的妞妞要上战场抵御侵略。
在妞妞上战场前, 村长牛牛给了妞妞N件装备, 妞妞需要选择其中的K件,装备在身上提升自己的战斗力。每件装备有5种属性增幅值,对于第i件装备它的属性增幅值为(ri1, ri2, ri3, ri4, ri5), 分别代表该装备对不同的属性值增幅。
当妞妞装备多件装备的时候,由于装备之前会互相影响, 对于每种属性值的增幅并不是所有装备该属性值之和, 而是该种属性值下所有装备中最大的属性值。而妞妞最终增加的战斗力为这5种属性值增幅之和。
妞妞一定要保卫牛家庄, 所以她希望她能提升尽可能多的战斗力, 请你帮帮她计算她最多能增加多少战斗力。
输入描述:
输入包括N+1行,
第一行包括两个正整数N和K(1 <= N <= 10000, 1 <= K <= N), 分别表示一共有的装备数量和妞妞需要选择的装备数量。
接下来的N行,每行5个整数ri1, ri2, ri3, ri4, ri5 (0 <= ri1, ri2, ri3, ri4, ri5 <= 10000)表示第i件装备的5种属性值增幅。
输出描述:
输出一个整数,表示妞妞最多能增加的战斗力。
输入例子1:
4 2 30 30 30 30 0 50 0 0 0 0 0 50 0 50 10 0 0 50 0 20
输出例子1:
170
例子说明1:
妞妞要从4件装备中选取2件, 如果妞妞选择第1件和第3件装备,那么增加的战斗力为30 + 50 + 30 + 50 + 10 = 170, 这是最大的方案。
【分析】:没有想到好办法,m大于等于5时取各个属性的最大值,m小于等于3时遍历,m等于4时为防止超时,用一点小小的技巧即可通过。
当k >= 5的时,每一维属性都取最大求和即可。
对于k < 5的时,预处理31种情况可能得到的最大的和。然后dfs枚举子集维护最大的答案即可。
【代码】:
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 int main() 5 { 6 int n, m; cin >> n >> m; 7 int **r = new int*[n], result = 0; 8 int maxr[5] = { 0 }; 9 for (int i = 0; i < n; i++) { 10 r[i] = new int[5]; 11 for (int j = 0; j < 5; j++) { 12 cin >> r[i][j]; 13 maxr[j] = max(maxr[j], r[i][j]); 14 } 15 } 16 if (m == 1) { 17 for (int i = 0; i < n; i++) { 18 int temp = 0; 19 for (int k = 0; k < 5; k++) { 20 temp += r[i][k]; 21 } 22 result = max(result, temp); 23 } 24 } 25 else if (m == 2) { 26 for (int i = 0; i < n; i++) { 27 for (int j = 0; j < n; j++) { 28 int temp = 0; 29 for (int k = 0; k < 5; k++) { 30 temp += max(r[i][k], r[j][k]); 31 } 32 result = max(result, temp); 33 } 34 } 35 } 36 else if (m == 3) { 37 for (int i = 0; i < n; i++) { 38 for (int j = 0; j < n; j++) { 39 for (int p = 0; p < n; p++) { 40 int temp = 0; 41 for (int k = 0; k < 5; k++) { 42 temp += max(max(r[i][k], r[j][k]), r[p][k]); 43 } 44 result = max(result, temp); 45 } 46 } 47 } 48 } 49 else if (m == 4) { 50 int maxtemp[5][5] = { 0 }; 51 for (int p = 0; p < 5; p++) { 52 for (int q = p + 1; q < 5; q++) { 53 int temp = 0; 54 for (int i = 0; i < n; i++) { 55 temp = max(temp, r[i][p] + r[i][q]); 56 } 57 for (int k = 0; k < 5; k++) { 58 if (k != p && k != q) { 59 temp += maxr[k]; 60 } 61 } 62 result = max(result, temp); 63 } 64 } 65 } 66 else { 67 for (int k = 0; k < 5; k++) { 68 result += maxr[k]; 69 } 70 } 71 cout << result; 72 return 0; 73 } 74 75 冗长
1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4 int main() 5 { 6 int n; cin >> n; 7 cout << (int)sqrt(n)*(int)sqrt(n) << endl; 8 return 0; 9 } 10 11 12 ////////////////////////////// 13 #include <bits/stdc++.h> 14 using namespace std; 15 16 int n; 17 int main() { 18 cin >> n; 19 int ans = 0; 20 for(int i = 0; i <= sqrt(n); i++) ans = i * i; 21 printf("%d ",ans); 22 return 0; 23 }