POJ2301——Beat the Spread!、POJ3624——Charm Bracelet（0-1背包）、POJ2479——Maximum sum

POJ2301——Beat the Spread!

题目描述

2301 -- Beat the Spread!

Description

Superbowl Sunday is nearly here. In order to pass the time waiting for the half-time commercials and wardrobe malfunctions, the local hackers have organized a betting pool on the game. Members place their bets on the sum of the two final scores, or on the absolute difference between the two scores.
Given the winning numbers for each type of bet, can you deduce the final scores?

Input

The first line of input contains n, the number of test cases. n lines follow, each representing a test case. Each test case gives s and d, non-negative integers representing the sum and (absolute) difference between the two final scores.

Output

For each test case, output a line giving the two final scores, largest first. If there are no such scores, output a line containing "impossible". Recall that football scores are always non-negative integers.

Sample Input

2
40 20
20 40

Sample Output

30 10
impossible

描述

超级碗周日即将到来。为了打发等待中场休息广告和衣橱故障的时间，当地的黑客组织了一个游戏投注池。会员将赌注押在两个最终比分的总和上，或两个比分之间的绝对差值上。
给定每种投注的中奖号码，您能推断出最终比分吗？

输入

输入的第一行包含 n，即测试用例的数量。N 行紧随其后，每行代表一个测试用例。每个测试用例都给出 s 和 d，非负整数，表示两个最终分数之间的和和（绝对）差。

输出

对于每个测试用例，输出一行，给出两个最终分数，最大在前。如果没有这样的分数，则输出包含 “impossible” 的行。回想一下，足球比分始终是非负整数。

样本输入

2
40 20
20 40

示例输出

30 10
impossible

运行代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    while (n--) {
        int s, d;
        cin >> s >> d;

        // 无解判断
        if (d > s || (s + d) % 2 != 0) {
            cout << "impossible" << endl;
            continue;
        }

        // 求解比分
        int a = (s + d) / 2;
        int b = (s - d) / 2;
        cout << a << " " << b << endl;
    }
    return 0;
}

代码思路

本题的核心问题是根据两个最终比分的和 s 以及它们的绝对差值 d 来推断出这两个最终比分。解题的关键在于建立数学模型来求解这两个比分，同时要考虑到足球比分是非负整数这一限制条件。

设两个最终比分分别为 x 和 y（假设 x >= y），根据题目条件可以得到以下两个方程：

1. 和的方程：x + y = s
2. 差的方程：x - y = d

将这两个方程相加，可以消去 y，得到 2x = s + d，即 x = (s + d) / 2。再将 x 的值代入第一个方程，可得 y = s - x = (s - d) / 2。

在求解过程中，需要考虑以下几种情况：

• 如果 d > s，那么根据 x - y = d 和 x + y = s，会出现矛盾，因为两个非负整数的差不可能大于它们的和，所以这种情况下无解。
• 如果 (s + d) 不是偶数，那么 (s + d) / 2 就不是整数，而足球比分必须是整数，所以这种情况下也无解。
• 如果 (s - d) 不是偶数，那么 (s - d) / 2 也不是整数，同样无解。

1. 输入处理：首先读取测试用例的数量 n。然后使用 while 循环处理每个测试用例，在循环中读取每个测试用例的和 s 以及绝对差值 d。

2. 无解判断：检查 d > s 或者 (s + d) 不是偶数的情况，如果满足这些条件，则输出 “impossible”，并使用 continue 跳过本次循环，处理下一个测试用例。

3. 求解比分：如果没有无解的情况，计算 a = (s + d) / 2 和 b = (s - d) / 2，其中 a 是较大的比分，b 是较小的比分。输出 a 和 b。

代码复杂度分析

• 时间复杂度：代码中使用了一个 while 循环来处理 n 个测试用例，对于每个测试用例，只进行了常数级别的运算，如比较、加法、除法等。因此，时间复杂度为 O(n)，其中 n 是测试用例的数量。

• 空间复杂度：代码中只使用了几个额外的变量 n、s、d、a 和 b，这些变量的数量是固定的，不随测试用例数量的增加而增加。因此，空间复杂度为 O(1)，即常数级别的空间复杂度。

POJ3624——Charm Bracelet（0-1背包）

题目描述

2506 -- Tiling3624 -- Charm Bracelet2506 -- Tiling

Description

Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

Input

* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di

Output

* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

Sample Input

4 6
1 4
2 6
3 12
2 7

Sample Output

2

描述

Bessie 去了商场的珠宝店，偷看了一个吊饰手镯。当然，她希望从 N （1 ≤ N ≤ 3,402） 个可用的魅力中尽可能地填充它。所提供列表中的每个超级按钮 i 都有一个权重 Wi （1 ≤ Wi ≤ 400）、一个“意愿”因子 Di （1 ≤ Di ≤ 100），并且最多可以使用一次。Bessie 只能支撑重量不超过 M （1 ≤ M ≤ 12,880） 的吊饰手链。

给定该权重限制作为约束条件，并给出 charm 及其权重和合意度等级的列表，推导出评级的最大可能总和。

输入

* 第 1 行：两个空格分隔的整数：N 和 M* 第 2 行.第 i+1 行使用两个空格分隔的整数描述charm i：W 和 Di

输出

* 第 1 行：一个整数，它是在权重限制下可以实现的最大魅力愿望之和

样本输入

4 6
1 4
2 6
3 12
2 7

示例输出

23

运行代码

#include <iostream>
#include <algorithm>
using namespace std;
const int M = 12881;
int main() {
    int n, m;
    cin >> n >> m;  // 输入物品数量 n 和背包容量 m
    int dp[M] = { 0 };  // 初始化 dp 数组，dp[j] 表示背包容量为 j 时的最大价值
    for (int i = 0; i < n; ++i) {  // 遍历每个物品
        int w, d;
        cin >> w >> d;  // 输入物品的重量 w 和价值 d
        for (int j = m; j >= w; --j) {  // 从背包容量 m 开始递减到 w
            dp[j] = max(dp[j], dp[j - w] + d);  // 状态转移方程
        }
    }
    cout << dp[m] << endl;  // 输出背包容量为 m 时的最大价值
    return 0;
}

代码思路

题目分析

这是一道典型的 0 - 1 背包问题。在 0 - 1 背包问题里，给定一组物品，每个物品有其对应的重量和价值，同时有一个容量固定的背包，要求从这些物品里挑选部分物品放入背包，使得背包内物品的总价值最大，并且物品总重量不能超过背包的容量，每个物品只能选择放入或者不放入背包，即 “0 - 1” 选择。

此问题可以借助动态规划算法来解决。动态规划的核心思想是把原问题分解成一系列子问题，然后通过求解子问题来得到原问题的解。

1. 定义状态：设 dp[j] 表示背包容量为 j 时所能获得的最大价值。
2. 初始化状态：dp[0] 到 dp[m] 都初始化为 0，这意味着当背包容量为 0 时，所能获得的最大价值为 0。
3. 状态转移方程：对于每个物品 i，其重量为 w，价值为 d，从背包容量 m 开始递减到 w，更新 dp[j] 的值，即 dp[j] = max(dp[j], dp[j - w] + d)。该方程的含义是，对于当前背包容量 j，有两种选择：不放入物品 i，此时最大价值就是 dp[j]；放入物品 i，此时最大价值是 dp[j - w] + d，我们选取这两种选择中的最大值。
4. 最终结果：当遍历完所有物品后，dp[m] 就是背包容量为 m 时所能获得的最大价值。

主函数逻辑

1. 输入部分：首先读取物品数量 n 和背包容量 m，接着依次读取每个物品的重量 w 和价值 d。
2. 动态规划部分：使用两层循环，外层循环遍历每个物品，内层循环从背包容量 m 开始递减到 w，更新 dp[j] 的值。
3. 输出部分：最后输出 dp[m]，也就是背包容量为 m 时所能获得的最大价值。

算法复杂度分析

• 时间复杂度：代码中有两层嵌套循环，外层循环遍历 n 个物品，内层循环从 m 递减到 w，所以时间复杂度为 O(n∗m)，其中 n 是物品的数量，m 是背包的容量。
• 空间复杂度：使用了一个长度为 m + 1 的数组 dp 来保存状态，因此空间复杂度为 O(m)。

POJ2479——Maximum sum

题目描述

1029 -- False coin2479 -- Maximum sum1029 -- False coin

Description

Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below:

Your task is to calculate d(A).

Input

The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input.
Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case.

Output

Print exactly one line for each test case. The line should contain the integer d(A).

Sample Input

1

10
1 -1 2 2 3 -3 4 -4 5 -5

Sample Output

13

Hint

In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer.
Huge input,scanf is recommended.

描述  description

给定一组 n 个整数：A={a1， a2,..., an}，我们定义一个函数 d（A），如下所示：您的任务是计算 d（A）。

输入

输入由 T（<=30） 个测试用例组成。测试用例数 （T） 在输入的第一行中给出。
每个测试用例包含两行。第一行是整数 n（2<=n<=50000）。第二行包含 n 个整数： a1， a2， ...， an. （|ai| <= 10000）。每个 case 后面都有一个空行。

输出

为每个测试用例打印一行。该行应包含整数 d（A）。

样本输入

1

10
1 -1 2 2 3 -3 4 -4 5 -5

示例输出

13

提示

在示例中，我们选择 {2,2,3，-3,4} 和 {5}，然后我们就可以得到答案。

输入量大，推荐使用 scanf。

这个题目非常容易超时，注意输入方式使用scanf

运行代码

代码一（时间超时）

#include <iostream>
#include <climits>
using namespace std;
const int N = 50010;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int a[N];
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        if (n < 2) {
            cout << "0\n";
            continue;
        }
        int max_left[N];
        int current_max = a[0];
        max_left[0] = a[0];
        for (int i = 1; i < n; ++i) {
            current_max = max(a[i], current_max + a[i]);
            max_left[i] = max(max_left[i - 1], current_max);
        }
        int max_right[N];
        current_max = a[n - 1];
        max_right[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            current_max = max(a[i], current_max + a[i]);
            max_right[i] = max(max_right[i + 1], current_max);
        }
        int res = INT_MIN;
        for (int k = 0; k < n - 1; ++k) {
            res = max(res, max_left[k] + max_right[k + 1]);
        }
        cout << res << '\n';
    }
    return 0;
}

代码二（AC）

#include <algorithm>
#include <climits>
using namespace std;

const int N = 50010;
int a[N], left_max[N], right_max[N];
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        // 预处理左侧最大子数组
        left_max[0] = a[0];
        int current = a[0];
        for (int i = 1; i < n; ++i) {
            current = max(a[i], current + a[i]);
            left_max[i] = max(left_max[i - 1], current);
        }
        // 预处理右侧最大子数组
        right_max[n - 1] = a[n - 1];
        current = a[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            current = max(a[i], current + a[i]);
            right_max[i] = max(right_max[i + 1], current);
        }
        // 计算最大组合和
        int res = INT_MIN;
        for (int i = 0; i < n - 1; ++i)
            res = max(res, left_max[i] + right_max[i + 1]);
        printf("%d\n", res);
    }
    return 0;
}

代码思路

代码一

1. 输入处理：
   • 首先读取测试用例的数量 T。
   • 对于每个测试用例，读取数组的长度 n 和数组元素 a[i]。
   • 如果 n < 2，直接输出 0 并进入下一个测试用例，因为根据题目要求，至少需要两个子数组，元素个数小于 2 时无法满足条件。
2. 计算前缀最大子数组和：
   • 定义数组 max_left[N] 用于存储从数组开头到每个位置的最大子数组和。
   • 初始化 current_max 为 a[0]，max_left[0] 也为 a[0]。
   • 通过遍历数组，使用动态规划的思想更新 current_max 和 max_left[i]。current_max 表示以当前位置 i 结尾的最大子数组和，max_left[i] 表示从数组开头到位置 i 的最大子数组和（包括当前位置）。
3. 计算后缀最大子数组和：
   • 定义数组 max_right[N] 用于存储从数组末尾到每个位置的最大子数组和。
   • 初始化 current_max 为 a[n - 1]，max_right[n - 1] 也为 a[n - 1]。
   • 通过反向遍历数组，使用动态规划的思想更新 current_max 和 max_right[i]。current_max 表示以当前位置 i 开头的最大子数组和，max_right[i] 表示从数组末尾到位置 i 的最大子数组和（包括当前位置）。
4. 计算最终结果：
   • 初始化结果变量 res 为 INT_MIN。
   • 通过遍历数组，计算 max_left[k] + max_right[k + 1] 的值，其中 k 的范围是 0 到 n - 2，取这些值中的最大值作为 res。
   • 输出 res 作为当前测试用例的结果。

算法分析

1. 时间复杂度：
   • 输入处理部分，读取测试用例和数组元素，时间复杂度为 O(T∗n)。
   • 计算前缀最大子数组和的循环，时间复杂度为 O(n)。
   • 计算后缀最大子数组和的循环，时间复杂度为 O(n)。
   • 计算最终结果的循环，时间复杂度为 O(n)。
   • 总体时间复杂度为 O(T∗n)，因为 T 是常数，所以近似为 O(n)。
2. 空间复杂度：除了输入数组 a[N] 外，额外使用了两个数组 max_left[N] 和 max_right[N] 来存储中间结果，所以空间复杂度为 O(n)。

该算法通过分别计算前缀最大子数组和与后缀最大子数组和，然后遍历数组找到两个不重叠子数组和的最大值。这种方法巧妙地利用动态规划减少了重复计算，有效地解决了题目中计算函数 d(A) 的问题。

代码二 

1. 头文件与全局变量：
   • 包含<algorithm> 头文件，用于使用max 等算法函数；包含<climits> 头文件，用于获取整数类型的极限值。
   • 定义了三个全局数组a[N]、left_max[N]、right_max[N]，分别用于存储输入的整数数组、从左侧开始的最大子数组和、从右侧开始的最大子数组和。
2. 输入处理：
   • 使用scanf 读取测试用例的数量T。
   • 对于每个测试用例，先读取数组的长度n，然后通过循环使用scanf 将n 个整数读入数组a 中。
3. 计算左侧最大子数组和：
   • 初始化left_max[0] 为a[0]，current 也为a[0]，current 用于记录以当前位置结尾的最大子数组和。
   • 通过循环遍历数组，从位置 1 开始。在每次循环中，更新current 为当前元素a[i] 与包含之前子数组和再加上当前元素两者中的较大值；然后更新left_max[i] 为left_max[i - 1] 与current 中的较大值，这样left_max[i] 就表示从数组开头到位置i 的最大子数组和。
4. 计算右侧最大子数组和：
   • 初始化right_max[n - 1] 为a[n - 1]，current 为a[n - 1]。
   • 通过反向循环遍历数组，从位置n - 2 开始。在每次循环中，更新current 为当前元素a[i] 与包含之后子数组和再加上当前元素两者中的较大值；然后更新right_max[i] 为right_max[i + 1] 与current 中的较大值，这样right_max[i] 就表示从数组末尾到位置i 的最大子数组和。
5. 计算最终结果并输出：
   • 初始化结果变量res 为INT_MIN。
   • 通过循环遍历，计算left_max[i] + right_max[i + 1] 的值，即左侧最大子数组和与右侧最大子数组和的组合和，取所有这些组合和中的最大值作为最终结果res。
   • 使用printf 将结果输出。

相对于代码一的改进点

1. 输入输出效率：代码一中使用cin 和cout 进行输入输出，通过ios::sync_with_stdio(false); 和cin.tie(0); 来提升效率。而此代码使用scanf 和printf 进行输入输出，在处理大量数据时，scanf 和printf 的效率通常比cin 和cout 更高，更符合题目中 “输入量大，推荐使用 scanf” 的提示。
2. 代码简洁性：此代码将数组定义为全局变量，减少了在每次循环中局部变量的创建，一定程度上简化了代码结构。不过全局变量过多可能会带来一些潜在问题，比如命名冲突等，使用时需谨慎。

代码二时间复杂度

主要由输入数据、计算左侧最大子数组和、计算右侧最大子数组和以及计算最大组合和这几个部分组成，下面对其时间复杂度进行分析：

1. 输入数据部分

scanf("%d", &T);
while (T--) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    //...
}

• 读取测试用例数量T，时间复杂度为O(1)。
• 对于每个测试用例，读取数组长度n，时间复杂度为O(1)。
• 接着通过循环读取n个整数到数组a中，循环执行n次，时间复杂度为O(n)。
• 由于有T个测试用例，这部分总的时间复杂度为O(T∗n)。因为题目中T <= 30，T可看作常数，所以近似为O(n)。

2. 计算左侧最大子数组和部分

left_max[0] = a[0];
int current = a[0];
for (int i = 1; i < n; ++i) {
    current = max(a[i], current + a[i]);
    left_max[i] = max(left_max[i - 1], current);
}

通过一个循环遍历数组来计算从左侧开始的最大子数组和，循环次数为n - 1次，时间复杂度为O(n)。

3. 计算右侧最大子数组和部分

right_max[n - 1] = a[n - 1];
current = a[n - 1];
for (int i = n - 2; i >= 0; --i) {
    current = max(a[i], current + a[i]);
    right_max[i] = max(right_max[i + 1], current);
}

通过反向循环遍历数组来计算从右侧开始的最大子数组和，循环次数为n - 1次，时间复杂度为O(n)。

4. 计算最大组合和部分

int res = INT_MIN;
for (int i = 0; i < n - 1; ++i)
    res = max(res, left_max[i] + right_max[i + 1]);

通过一个循环计算不同分割点下左侧最大子数组和与右侧最大子数组和的组合和，并取最大值，循环次数为n - 1次，时间复杂度为O(n)。

总体时间复杂度

将上述各部分时间复杂度综合起来，因为输入数据、计算左侧最大子数组和、计算右侧最大子数组和以及计算最大组合和这几个部分的时间复杂度都是O(n)级别，其中主导部分的时间复杂度决定整体复杂度，所以代码二的时间复杂度为O(n)。