Yaroslav has an array, consisting of (2·n-1) integers. In a single operation Yaroslav can change the sign of exactly n elements in the array. In other words, in one operation Yaroslav can select exactly n array elements, and multiply each of them by -1.
Yaroslav is now wondering: what maximum sum of array elements can be obtained if it is allowed to perform any number of described operations?
Help Yaroslav. Input
The first line contains an integer n (2≤n≤100). The second line contains (2·n-1) integers — the array elements. The array elements do not exceed 1000 in their absolute value. Output
In a single line print the answer to the problem — the maximum sum that Yaroslav can get. Sample test(s) Input
2 50 50 50
Output
150
Input
2 -1 -100 -1
Output
100
Note
In the first sample you do not need to change anything. The sum of elements equals 150.
In the second sample you need to change the sign of the first two elements. Then we get the sum of the elements equal to 100.
2*n-1个数,每次可以选择n个数,改变它们的符号 可以发现,当n是奇数,我们可以令任意数目的数改变符号 当n是偶数,我们可以使得2*k对数改变符号,这里枚举下求个最大值就行
/*************************************************************************> File Name: cf-182-c.cpp> Author: ALex> Mail: zchao1995@gmail.com> Created Time: 2015年05月06日 星期三 20时22分21秒 ************************************************************************/;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> PLL;int arr[220];int main() {int n;while (~scanf(“%d”, &n)) {int cnt1 = 0, cnt2 = 0;for (int i = 1; i <= 2 * n – 1; ++i) {scanf(“%d”, &arr[i]);if (arr[i] < 0) {++cnt1;}else {++cnt2;}}sort(arr + 1, arr + 2 * n);if (n & 1) {int sum = 0;for (int i = 1; i <= 2 * n – 1; ++i) {sum += abs(arr[i]);}printf(“%d\n”, sum);}else {int sum = 0;if (cnt1 & 1) {for (int k = 0; 2 * k <= 2 * n – 1; ++k) {int tmp = 0;for (int i = 1; i <= 2 * n – 1; ++i) {if (i <= k * 2) {tmp -= arr[i];}else {tmp += arr[i];}}sum = max(sum, tmp);}}else {for (int i = 1; i <= 2 * n – 1; ++i) {sum += abs(arr[i]);}}printf(“%d\n”, sum);}}return 0;}
，路遥知马力，日久见人心。
