题目链接：10747 - Maximum Subsequence
题目大意：给出n个数，从中选取k个，使得乘积最大，并且尽量使和最大。
解题思路：首先按照数的绝对值大小排序。然后就要分三大类情况讨论：
（1）前k个中选到0：如果选到0的话，乘积一定是0，所以尽量选大的数，让和变大。
（2）前k个中选到负数的个数为偶数：这样的话直接输出答案（一定为最优解）
（3）前k个中选到的负数个数为奇数：这类情况比较复杂，还要分成两个子类：
a）k个中没有正数（意味着不能用未选的数中的负数来替换）：
如果还正数：优先用正数替换最小的负数；否则注定乘积为负数或者0：选最大的k个。
b）k个中有正数：
还有正数和负数：比较最优； 只有正数：选用负数； 只有负数：选用正数； 只有0：选最大的k个，注意0一定要选。
对应的数据：
6 3 -5 -4 -3 -2 2 1
6 3 -5 -4 -3 -2 -1 0
6 3 -5 -4 -3 -2 -2 -1
6 3 5 4 -3 2 -1 1
6 3 5 -4 3 -2 1 1
6 3 5 4 -4 -2 2 1
6 3 5 4 -3 1 1 1
6 3 5 4 -3 -1 -1 -1
4 3 5 4 -3 0
答案：
-7
-3
-5
11
-1
11
10
1
9
#include#include #include #include #include using namespace std; const int N = 10005; int n, k, num[N]; bool cmp(const int& a, const int& b) { int p = abs(a), q = abs(b); if (p != q) return p > q; else return a > b; } void init() { for (int i = 0; i < n; i++) scanf("%d", &num[i]); sort(num, num + n, cmp); } int handle(int t) { sort(num, num + n); int sum = 0; for (int i = 1; i <= t; i++) { sum += num[n-i]; } return sum; } int solve() { int sum = 0, cnt = 0, p = 0, q = 0; bool flag = false; for (int i = 0; i < k; i++) { if (num[i] == 0) { flag = true; break; } else if (num[i] < 0) { cnt++; q = num[i]; } else p = num[i]; sum += num[i]; } if (flag) return handle(k); else if (cnt % 2 && k < n) { int x = 0, y = 0, bo = 0; for (int i = k; i < n; i++) if (num[i] > 0) { x = num[i]; break; } for (int i = k; i < n; i++) if (num[i] < 0) { y = num[i]; break; } for (int i = k; i < n; i++) if (num[i] == 0) { bo = 1; break; } if (p == 0) { if (x) sum = sum - q + x; else sum = handle(k); } else { if (x == 0 && y == 0) sum = handle(k - 1); else if (x == 0) sum = sum - p + y; else if (y == 0) sum = sum - q + x; else if (x * p >= y * q) sum = sum - q + x; else sum = sum - p + y; } } return sum; } int main() { while (scanf("%d%d", &n, &k) == 2 && n + k) { init(); printf("%d\n", solve()); } return 0; }