D - Patisserie ABC 枚举状态 加 贪心
Time limit : 2sec / Memory limit : 1000MB
Score: 400 points
Problem Statement
Takahashi became a pastry chef and opened a shop La Confiserie d'ABC to celebrate AtCoder Beginner Contest 100.
The shop sells N kinds of cakes.
Each kind of cake has three parameters "beauty", "tastiness" and "popularity". The i-th kind of cake has the beauty of xi, the tastiness of yi and the popularity of zi.
These values may be zero or negative.
Ringo has decided to have M pieces of cakes here. He will choose the set of cakes as follows:
- Do not have two or more pieces of the same kind of cake.
- Under the condition above, choose the set of cakes to maximize (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity).
Find the maximum possible value of (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) for the set of cakes that Ringo chooses.
Constraints
- N is an integer between 1 and 1 000 (inclusive).
- M is an integer between 0 and N (inclusive).
- xi,yi,zi (1≤i≤N) are integers between ?10 000 000 000 and 10 000 000 000 (inclusive).
Input
Input is given from Standard Input in the following format:
N M
x1 y1 z1
x2 y2 z2: :
xN yN zN
Output
Print the maximum possible value of (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) for the set of cakes that Ringo chooses.
Sample Input 1
Copy
5 3
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
Sample Output 1
Copy
56
Consider having the 2-nd, 4-th and 5-th kinds of cakes. The total beauty, tastiness and popularity will be as follows:
- Beauty: 1+3+9=13
- Tastiness: 5+5+7=17
- Popularity: 9+8+9=26
The value (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) here is 13+17+26=56. This is the maximum value.
Sample Input 2
Copy
5 3
1 -2 3
-4 5 -6
7 -8 -9
-10 11 -12
13 -14 15
Sample Output 2
Copy
54
Consider having the 1-st, 3-rd and 5-th kinds of cakes. The total beauty, tastiness and popularity will be as follows:
- Beauty: 1+7+13=21
- Tastiness: (?2)+(?8)+(?14)=?24
- Popularity: 3+(?9)+15=9
The value (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) here is 21+24+9=54. This is the maximum value.
Sample Input 3
Copy
10 5
10 -80 21
23 8 38
-94 28 11
-26 -2 18
-69 72 79
-26 -86 -54
-72 -50 59
21 65 -32
40 -94 87
-62 18 82
Sample Output 3
Copy
638
If we have the 3-rd, 4-th, 5-th, 7-th and 10-th kinds of cakes, the total beauty, tastiness and popularity will be ?323, 66 and 249, respectively.
The value (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) here is 323+66+249=638. This is the maximum value.
Sample Input 4
Copy
3 2
2000000000 -9000000000 4000000000
7000000000 -5000000000 3000000000
6000000000 -1000000000 8000000000
Sample Output 4
Copy
30000000000
The values of the beauty, tastiness and popularity of the cakes and the value to be printed may not fit into 32-bit integers.
给你n个蛋糕，我们可以从中选择m个，每个蛋糕都有三列价值（正负都有），先让你求选择m个蛋糕的最大价值，
即竖列的价值相加，如果有负数，就取绝对值，得到的和再相加。
思路：只有1000个蛋糕，每个蛋糕的三个价值也只有八种状态，就是
--- +++ --+ -++ -+- +-- ++- +-+
所以对于每个蛋糕我们可以枚举他的价值贡献的可能，然后取一个最大值，接着对n个蛋糕的总价值
排序一遍，取前m个即可
代码如下：
#include <bits/stdc++.h>using namespace std;const int maxn = 2000;
struct node {long long a,b,c,s;
} g[maxn];
int n,m;
long long s[maxn];
long long calc(int flag1,int flag2,int flag3,int i ) {long long ans = 0;if(flag1) ans += g[i].a;else ans -= g[i].a;if(flag2) ans += g[i].b;else ans -= g[i].b;if(flag3) ans += g[i].c;else ans -= g[i].c;return ans;
}bool cmp(long long a,long long b) {return a > b;
}long long getMax(int a,int b,int c) {for(int i = 1; i <= n; i++)s[i] = calc(a,b,c,i);sort(s + 1,s + 1 + n,cmp);long long sum = 0;for(int i = 1; i <= m; i++)sum += s[i];return sum;
}
int main() {while(cin >> n >> m) {memset(s,0,sizeof(s));long long ans = 0;for(int i = 1; i <= n; i++) cin >> g[i].a >> g[i].b >> g[i].c,g[i].s = g[i].a + g[i].b + g[i].c;ans = max(ans,getMax(1,1,1));ans = max(ans,getMax(1,1,0));ans = max(ans,getMax(1,0,1));ans = max(ans,getMax(0,1,1));ans = max(ans,getMax(1,0,0));ans = max(ans,getMax(0,0,1));ans = max(ans,getMax(0,1,0));ans = max(ans,getMax(0,0,0));cout << ans << endl;}return 0;
}