UVA10891 Game of Sum

区间dp

2.UVA10891 Game of Sum

题目描述

有一个长度为 $n$ 的整数序列，两个游戏者 $A$ 和 $B$ 轮流取数，$A$ 先取。每次玩家只能从左端或者右端取任意数量的数，但不能两边都取。所有数都被取走视为游戏结束，然后统计每个人取走的数之和，作为各自的得分。两个人采取的策略都是让自己得分尽可能高，并且两个人都很机智，求 $A$ 得分 - $B$ 得分后的结果。

输入格式

输入包含多组数据，每组数据第一行为正整数 $n(1\leq n\leq 100)$ ，第二行为给定的整数序列，输入结束标志是 $n=0$ 。

输出格式

对于每组数据，输出 $A$ 和 $B$ 都采取最优策略下，$A$ 的得分$-B$ 的得分。

题目分析

因为取数字的操作只能在头和尾进行，那么其在任意时候都是一个连续的序列，记$dp[l][r]$为先手在$l,r$这个子序列中获得的最大分数，那么很容易想到$n^3$暴力区间dp，状态转移方程为$dp[l][r]=sum[l][r]-min(dp[l][l+1],dp[l][l+2]....dp[l][r],dp[r][r],dp[r-1][r],dp[r-2][r]...dp[l][r])$答案为$dp[1][n]+(sum[n]-dp[1][n])$，考虑如何写$n^2$，观察到状态转移方程中有两坨东西，这坨东西可以在状态转移的时候记录在另一个数组里，然后就完成了优化，直接变成$O(n^2)$

代码

//
// Created by mrx on 2022/9/24.
//
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>

using ll = long long;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	int n;
	while (std::cin >> n && n) {
		std::vector<int> a(n + 1);
		for (int i = 1; i <= n; ++i)std::cin >> a[i];
		std::vector<int> sum(n + 1);
		for (int i = 1; i <= n; ++i)sum[i] = sum[i - 1] + a[i];
		std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1, 0));
		std::vector<int> lmin(n + 1, 0x3f3f3f3f), rmin(n + 1, 0x3f3f3f3f);

		for (int len = 1; len <= n; ++len) {
			for (int l = 1; l + len - 1 <= n; ++l) {
				int r = l + len - 1;
				dp[l][r] = sum[r] - sum[l - 1] - std::min({0, lmin[l], rmin[r]});
				lmin[l] = std::min(lmin[l], dp[l][r]);
				rmin[r] = std::min(rmin[r], dp[l][r]);
			}
		}
		std::cout << 2 * dp[1][n] - sum[n] << '\n';
	}
	return 0;
}