目录

数字序列博弈游戏

A和B两个人进行博弈游戏。有一个非递减数字序列，由A先手，每次选择一个当前序列中的数字，把该数字在序列中第一次出现的位置及其左边的数字全部删除，当某人操作完之后序列为空时则此人胜利。对给定的序列输出获胜的人。

输入描述
第一行一个整数t表示测试用例组数
对每组数据，第一行一个整数n表示序列中数字个数
接下来一行n个整数，表示序列中的数字

示例

输入：
1
5
2 2 3 3 6
输出：
A
解释：
A先手直接选6，序列直接清空，故A胜

思路1

只有当序列中所有数字的个数都为偶数时，后手的人才能获胜，其余情况先手的人获胜。

代码1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

t = int(input())
for _ in range(t):
    n = int(input())
    nums = [int(x) for x in input().split()]
    tmp = 1
    hasOdd = False # 记录是否有个数为奇数的数字
    for i in range(1, n):
        if nums[i] != nums[i-1]:
            if tmp & 1:
                hasOdd = True
                break
            tmp = 1
        else:
            tmp += 1
    # 此时tmp是最后一个数字的个数
    if hasOdd or tmp & 1:
        print("A")
    else:
        print("B")

二维背包问题

Codeforces 148E

一个n层的柜子，每层摆放有价值的物品。可以从这个柜子里拿m个物品，每次只能从某层的两端中选拿一个物品，求可以拿到的最大价值。

输入描述
第一行两个正整数n,m，表示柜子层数和可拿物品次数。
接下来n行，每行先输入一个数字x，表示该层物品个数，接下来输入x个正整数，表示每个物品的价值v。
其中1 <= n, x, v <= 100, 1 <= m <= 10000

示例

输入：
2 3
2 3 2
4 1 4 1 5
输出：
10
解释：
选择第1层的两个物品，和第2层的第4个物品可获得最大价值10

思路1

假设最佳方案中，在第i层柜子中需要拿j个物品，那么在第i层拿j个物品的最大价值记为w[i][j]。
对每一层拿j个物品会有三种拿法：

  • 全从左边拿j个
  • 全从右边拿j个
  • 左边拿一部分k个，右边拿一部分(j-k)个。

实际上，第三种拿法中，k设为j和0就是第一种和第二种拿法。这里用前缀和来求w[i][j]，假设第i层有cnt个物品，要从该层拿j个，v[i][k]表示第i层前k个物品的价值总和，则左边拿k个的价值总和为v[i][k]，右边拿(j-k)个的价值总和为 v[i][cnt] - v[i][cnt-(j-k)]，则有：

w[i][j] = max(v[i][k] + v[i][cnt] - v[i][cnt-(j-k)]), $k \in [0, j]$

求出每层拿出j个物品可获得的最大价值后，问题即转化为从每层拿出多少个物品，最后总和为m个物品可获得的最大价值，这是一个背包问题，用DP求解。设dp[i][j]为在前i层共拿了j个物品的最大价值，即如果在前i层共取了j个物品，在第i层取k个物品，则应在前i-1层取j-k个物品。则转移状态方程为：

dp[i][j] = max(dp[i-1][j-k] + w[i][k])， $k \in [0, min(cnt_{i}, j)]$, $j \in [0, m]$

代码1

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] v = new int[101][10001];
        int[][] w = new int[101][10001];

        for (int i = 0; i < n; i++) {
            int cnt = in.nextInt();
            v[i][0] = 0;
            for (int j = 1; j <= cnt; j++) {
                v[i][j] = in.nextInt();
                v[i][j] += v[i][j-1]; // 前缀和
            }
            w[i][0] = 0;
            for (int j = 1; j <= cnt; j++) {
                for (int k = 0; k <= j; k++) {
                    w[i][j] = Math.max(w[i][j], v[i][k]+v[i][cnt]-v[i][cnt-(j-k)]);
                }
            }
            v[i][0] = cnt;
        }
        int[][] dp = new int[n][m+1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= v[i][0] && k <= j; k++) {
                    if (i == 0) {
                        dp[i][j] = Math.max(dp[i][j], w[i][k]);
                    } else {
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j-k]+w[i][k]));
                    }
                }
            }
        }
        System.out.print(dp[n-1][m]);
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <vector>
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

int v[101][10001], w[101][10001], dp[101][10001];

int main() {
	int n, m, num;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int j = 0;
		int tmp;
		while (cin >> tmp) {
			v[i][j] = tmp;
			j++;
			if (cin.get() == '\n') break;
		}
		int cnt = v[i][0];
		v[i][0] = 0;
		for (int j = 1; j <= cnt; j++) {
			v[i][j] += v[i][j - 1];
		}
		w[i][0] = 0;
		for (int j = 1; j <= cnt; j++) {
			for (int k = 0; k <= j; k++) {
				w[i][j] = max(w[i][j], v[i][k] + v[i][cnt] - v[i][cnt - (j - k)]);
			}
		}
		v[i][0] = cnt;
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= m; j++) {
			for (int k = 0; k <= v[i][0] && k <= j; k++) {
				if (i == 0) {
					dp[i][j] = max(dp[i][j], w[i][k]);
				}
				else {
					dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + w[i][k]));
				}
			}
		}
	}
	cout << dp[n-1][m] << endl;
}

Python3 超时：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

n, m = [int(x) for x in input().split()]
v = []
w = []
for i in range(n):
    cur = [int(x) for x in input().split()]
    cnt = cur[0]
    v.append([0])
    for j in range(1, cnt+1):
        v[i].append(cur[j])
        v[i][j] += v[i][j-1]
    w.append([0] * (cnt + 1))
    for j in range(1, cnt+1):
        for k in range(j+1):
            w[i][j] = max(w[i][j], v[i][k] + v[i][cnt] - v[i][cnt-(j-k)])
    v[i][0] = cnt
dp = [[0] * (m+1) for _ in range(n)]
for i in range(n):
    for j in range(m+1):
        k = 0
        while k <= v[i][0] and k <= j:
            if i == 0:
                dp[i][j] = max(dp[i][j], w[i][k])
            else:
                dp[i][j] = max(dp[i][j], dp[i-1][j-k] + w[i][k])
            k += 1
print(dp[n-1][m])