CF1927G. Paint Charges

Problem - 1927G - Codeforces

• 做这道题的时候自己把 \(dp\) 式子卡的太死了，导致怎么想都想不出来，但正解的 \(dp\) 设的是很宽松的

• 设 \(dp_{i,j,k}\) 表示考虑前 \(i\) 个数，所有中第一个没被染色的是 \(j\)，在 \(i\) 后面第一个没被染到的是 \(k\)

• 转移就判断第 \(i\) 个数向左向右还是不选即可

• \(O(n^3)\)

• 这个题还可以 \(O(n^2)\)，而且和 \(O(n^3)\) 的式子好像几乎没什么关系

• 设 \(f_i\) 表示让 \(1 \sim i\) 染上颜色的最少操作次数

• 发现有三种可能：

  • 让 \(i\) 向左边染色，\(f_i = \min\limits_{j = l_i}^{i} f_{j - 1}\)

  • 让 \(j\) 向右边染色覆盖过 \(i\)，\(f_i = \min\limits_{j = 1 \& r[j] \geq i}^{ i - 1} f_{j - 1}\)

  • 让 \(j\) 向右覆盖过 \(i\)，在 \([j,i]\) 中找一点 \(k\) 向左覆盖过 \(j\)，转移挺难写的略

• 直接转移即可，第三种要通过改变枚举顺序简单优化一下

• 复杂度 \(O(n^2)\)

#include<bits/stdc++.h>
#define ll long long
#define ckmin(a, b) (a = min(a, b))
#define ckmax(a, b) (a = max(a, b))
#define pcn putchar('\n');
using namespace std;
template<typename T>T &read(T &x){
	cin >> x;
	return x;
}

const int maxn = 150;

int n, l[maxn], r[maxn];
int dp[maxn];

void mian(int TwT){
	read(n);
	int a;
	for(int i = 1; i <= n; ++ i){
		read(a);
		l[i] = max(i - a + 1, 1);
		r[i] = min(i + a - 1, n);
	}
	
	for(int i = 1; i <= n; ++ i){
		dp[i] = n + 5;
	}
	dp[0] = 0;
	
	for(int i = 1; i <= n; ++ i){
		for(int j = l[i]; j <= i; ++ j){
			ckmin(dp[i], dp[j - 1] + 1);
		}
		
		for(int j = 1; j <= i; ++ j){
			if(r[j] < i) continue;
			
			ckmin(dp[i], dp[j - 1] + 1);
		}
		
		int L = i + 1, R = i, x = i;
		
		for(int j = i - 1; j >= 1; -- j){
			if(r[j] < i) continue;
			
			R = min(L - 1, j);
			
			for(; x > j; -- x){
				if(l[x] > j) continue;
				
				ckmin(L, l[x]);
			}
			
			for(int k = L; k <= R; ++ k){
				ckmin(dp[i], dp[k - 1] + 2);
			}
		}
	}
	
//	for(int i = 1; i <= n; ++ i){
//		printf("%d ", dp[i]);
//	}
//	pcn;
	
	printf("%d\n", dp[n]);
}

void init(int TwT){
	
}

int main(){
	
	int T = 1;
	read(T);
	
	for(int TwT = 1; TwT <= T; ++ TwT){
		init(TwT);
		mian(TwT);
	}
	
	return 0;
}
/*
1
2
2 1
*/