XYD1005CSPS

标签：le int max sum 答案 inf XYD1005CSPS

T1 传送门 [最短路，二分答案]

Description

无向连通图，求出一个最小的 \(x\)，使得每两点之间存在一条路径可以划分成不超过 \(k\) 段路径，且每段路径长度不超过 \(x\)，只能从节点处切割，不能从边中间划分。
\(n\le 100\)，无重边自环。

Solution

\(n\) 非常小，又要考虑 每两个点，自然想到全源最短路 floyd。
先预处理出每两个点之间的最短路，然后做二分答案。
对于每次 check，我们可以把最短路径不超过 mid 的两个点连接，构建一个新图，边权为 \(1\)。
显然在新图上再跑一遍 floyd，判断是否能划分成不超过 \(k\) 段即可。
复杂度 \(O(n^3log_2n)\)。

Summary

二分答案不难想到，重点在于如何巧妙处理。

T2 棋盘 [DP]

Description

给定一个 \(n\) 行 \(m\) 列的矩阵，每个位置有一个权值 \(a_{i,j}\)，有两个人 A 和 B，A 会在第一行选择一个位置开始上下左右移动，B 每次会在两行之间的某个位置横着放一堵墙阻挡 A 的移动，且不能完全堵死 A 的下移路径，当 A 走到最后一行游戏结束，A 要求走过的权值之和尽量小，B 要求 A 走过的权值之和尽量大，每次 A B 都按照最优策略操作，求最后 A 的路径的权值和。
\(n\)，\(m\le 100\)。

Solution

性质\(1\)：A 不会往上走。

性质\(2\)：可以往下时 A 一定会往下走，因为根据 B 的最优策略，肯定是控制 A 从一个地方下来，使得答案最大，如果 A 此时不往下走，那么 B 完全可以把其他路堵死，强迫 A 走这条路，那么 A 与其绕一圈回来，不如直接往下走。

性质\(3\)：根据以上结论，显然 B 在每一行放的墙是一段区间。

性质\(4\)：A 可以选择向左或向右走然后折返回来以达到最优策略。

推出以上性质，我们就把一个凌乱无章的，每个点可以走四个方向，每个点可以选择放不放墙的不公平博弈游戏，抽取出了其有用状态，

设 \(f(i,l,r,0)\) 表示当前是第 \(i\) 行，B 在 \((l,r]\) 放了墙，A 此时在 \(l\) 的最优答案，相当于 A 从 \(r\) 走到 \(l\)，
\(f(i,l,r,1)\) 表示当前是第 \(i\) 行，B 在 \([l,r)\) 放了墙，A 此时在 \(r\) 的最优答案，相当于 A 从 \(l\) 走到 \(r\)。

考虑如下转移：

• 边界：\(f(n,i,i,0/1)=a(n,i)\)。
• 由于是否向下走是 B 控制的，但 A 可以选择向左或向右，所以转移应该形如这样的形式 \(f(*,*,*,0)=\max(直接向下，\min(从左走到右，继续往左))\)，\(f(*,*,*,1)=\max(直接向下，\min(从右走到左，继续往右))\)。
• \(f(i,l,r,0)=\max(a(i,l)+f(i+1,l,l,0),\min(sum(l,r)+f(i,l,r+1,1),a(i,l)+f(i,l-1,r,0)))\)，\(f(i,l,r,1)\) 类似。
• 答案：\(\max(f(1,i,i,0))\)。
• 从下往上遍历，从大区间往小区间遍历即可。

Code

const int N = 1e2 + 5, inf = 1e9;

int n, m, a[N][N];
int sum[N][N], f[N][N][N][2];

int getSum(int i, int l, int r) {return sum[i][r] - sum[i][l - 1];}

void Solve(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> a[i][j];
			sum[i][j] = sum[i][j - 1] + a[i][j];
		}
	}

	for(int i = 1; i <= m; i++) f[n][i][i][0] = f[n][i][i][1] = a[n][i]; // 边界
	for(int i = n - 1; i >= 1; i--){
		for(int l = 1; l <= m; l++){
			for(int r = m; r >= l; r--){
				// 直接向下走
				f[i][l][r][0] = a[i][l] + f[i + 1][l][l][0];
				f[i][l][r][1] = a[i][r] + f[i + 1][r][r][1];

				if(l == 1 && r == m) continue; // 只能向下走

				// 在左边，向右走
				int fl = getSum(i, l, r) + (r < m ? f[i][l][r + 1][1] : inf);
				// 在左边，向左走
				fl = min(fl, a[i][l] + (l > 1 ? f[i][l - 1][r][0] : inf));

				// 在右边，向左走
				int fr = getSum(i, l, r) + (l > 1 ? f[i][l - 1][r][0] : inf);
				// 在右边，向右走
				fr = min(fr, a[i][r] + (r < m ? f[i][l][r + 1][1] : inf));

				// 合并
				f[i][l][r][0] = max(f[i][l][r][0], fl);
				f[i][l][r][1] = max(f[i][l][r][1], fr);
			}
		}
	}

	// 统计答案
	int ans = inf;
	for(int i = 1; i <= m; i++) ans = min(ans, f[1][i][i][0]);
	cout << ans << endl;
}

Summary

个人认为非常有意思的 DP 题，需要多手模样例推性质（考场上想严谨数学证明真的很难，还是要手模样例），还需要巧妙地抽取有用状态，设计转移。
但这题考场上想了一个假做法，向左或向右不一定要走到底才回来，也可以是中途折返，于是便有了 \((l,r)\)。
所以一定要学好 DP 啊。T_T
感谢机房 dalao szh 提供的 hack。

T3 入侵者 [反悔贪心]

Description

有 \(n\) 个怪物 \((h_i,p_i)\)，选择打怪顺序，如果收到之前受到的总伤害不超过 \(h_i\)，那么可以击败这个怪物，收到伤害加 \(p_i\)，输出最大化的击败数量。

Solution

\(h\) 可以看作是截止时间，\(p\) 可以看作是花费时间，于是这就是一道反悔贪心。
按照正常套路我们肯定按照 \(h\) 升序排序。
但是和 P4053 建筑抢修 不同的是，后者是在截止之前做完，前者是在截止之前开始。所以对于这道题，我们花费的时间不止影响在截止时间之内，还会往后影响。于是转换一下，变为在 \((h+p)\) 截止，花费 \(p\) 时间。
所以按照 \((h+p)\) 截止时间升序排序即可。

（简略）证明：
考虑怪物 \(i\) 和 \(j\)，假设 \(j\) 放在 \(i\) 之前能打完两只怪，\(i\) 放在 \(j\) 之前只能打完一只怪，于是便有如下关系式，（\(h\) 表示当前受到总伤害），
\(h\le h_j\)，\(h+p_j\le h_i\)，
\(h\le h_i\)，\(h+p_i>h_j\)，
合并后两项，
\(h_j-p_i<h\le h_i-p_j\)，
\(h_j+p_j\le h_i+p_i\)，
由于都是整数，因此这样表示并没有多大影响。
于是按照 \((h+p)\) 升序排序即可取到最优答案，
证毕。

Summary

反悔贪心板子题，但赛时对于排序没有考虑周全。

标签：le,int,max,sum,答案,inf,XYD1005CSPS
From： https://www.cnblogs.com/chenwenmo/p/18451489