Codeforces 1453F Even Harder

题目链接

点我跳转

题目大意

给定 (n) 个关卡 , 第 (i) 个关卡有个权值为 (ai) 的传送门

当你在第 (i) 个关卡时 , 如果 (ai = 0) 并且 (i!=n) ，则你闯关失败

否则你可以跳到 (i + 1) ~ (i + ai) 中的任意关卡 ( (ai + i <= n) )

当你到达第 (n) 关时，闯关结束

但为了增加闯关难度，系统要求你删除最少的传送门( 即令 (ai = 0) )

使得从第一关开始，有且仅有一条可行的通关路线

解题思路

定义 (dp[i][x]) 为最小删除次数 , 使得从起点出发 , 只有一条可行路 , 这条可行路的终点为 (i)

(i) 点的上一个点 (设为 (j)) 最远能到达的位置是 (x) (其中 (j + a[j] >= i))

因为上一个点是 (j) , 且只有一条路

那么对于 (k ∈[1,j-1]) , 如果 (k + a[k] >= i) ，需要把 (k) 删除

对于 (k ∈[j + 1 , i - 1]) 如果 (k + a[k] >= i) ，需要把 (k) 删除

记 (1) ~ (j-1) 需要删除的 (k) 的个数为 (pre) , (j+1) ~ (i-1) 需要删除的 (k) 的个数为 (suf)

那么 $dp[i][j + a[j]] = pre + suf $

对于 (suf) 可以从 (i - 1) 到 (1) 枚举，每次碰到一个 (k + a[k] >= i，suf ++)

对于 (pre) 它等于 (min( dp[j][i - 1] , dp[j][i - 2] ... dp[j][1]))

其含义如下：

最小删除次数

使得从起点出发，有一条可行路 , 这条可行路的终点为 (j)

而 (j) 点的上一个点 (k) 最远能到达的位置是 (i-1、i-2、i-3 ... 1) (即 (a[k] + k < i))

对于 (pre) 的转移如果需要枚举 (i - 1 , i - 2 , ... , 1) 那么就多了一层循环 , (Tle) 警告

而不难发现我们只需要找到最小的满足条件 (a[k] + k < i) 的 (dp[j][x] , x ∈[1 , i - 1])

所以我们可以维护一个前缀最小值 , 即 $dp[i][j] = min(dp[i][j] , dp[i][j - 1] $

那么显然 (pre = dp[j][i - 1])

最后答案为 (dp[n][n]) (从起点开始只有一条可行路线 , 路的终点为 (n) , (n) 的上一个点最远能达到的距离为 (n))

AC_Code

#include<bits/stdc++.h>
using namespace std;
const int N = 3e3 + 10;
int n , a[N] , dp[N][N];
signed main()
{
	int T = 1;
	cin >> T;
	while(T --)
	{
		cin >> n;
		for(int i = 1 ; i <= n ; i ++) cin >> a[i];
		for(int i = 2 ; i <= n ; i ++) for(int j = 1 ; j <= n ; j ++) dp[i][j] = 2e9; //起点不能删除所以从 2 开始 
		for(int i = 2 ; i <= n ; i ++)
		{
			int suf = 0;
			for(int j = i - 1 ; j >= 1 ; j --)
			{
				if(j + a[j] >= i)
				{
					int pre = dp[j][i - 1];
					dp[i][j + a[j]] = min(dp[i][j + a[j]] , pre + suf);
					suf ++ ; 	
				} 
		 	}
			for(int j = i ; j <= n ; j ++) dp[i][j] = min(dp[i][j] , dp[i][j - 1]);
		}
		cout << dp[n][n] << '
';
	}
	return 0;
}