qbxt DAY4 T3

qbxt DAY4 T3

\(k=1\)

考虑动态规划

设\(f[i][j]\)表示涂到点\(i\)，这个点涂的颜色是\(j\)的最小代价

转移就枚举上一个点涂的颜色

\(f[i][j]=min(f[i-1][k])(k!=j)=min(\min\limits_{k<j}(f[i-1][k]), \min\limits_{k>j}(f[i-1][k]))\)

后面的式子可以直接前缀和优化。维护\(f[i][j]\)的前缀最小值和后缀最小值，复杂度\(O(n^2)\)

\(60pts\)

枚举相同颜色的区间\((l,r)\)和颜色\(t\)，枚举量为\(O(nmk)\)

设\(f[i][j]\)表示前\(i\)个格子已经染色，并且这个格子不能染成\(j\)的最小代价

\(g[i][j]\)表示后\(i\)个格子已经染色，并且这个格子不能染成\(j\)的最小代价

分别对\(f\)和\(j\)进行上述的前缀和优化

	memset(f, 0x3f, sizeof(f));
	memset(fl, 0x3f, sizeof(fl));
	memset(fr, 0x3f, sizeof(fr));
	for(int j = 1; j <= m; j ++) f[0][j] = fl[0][j] = fr[0][j] = 0;
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= m; j ++)
			f[i][j] = cost[i][j] + min(fl[i - 1][j - 1], fr[i - 1][j + 1]);
		for(int j = 1; j <= m; j ++)
			fl[i][j] = min(f[i][j], fl[i][j - 1]);
		for(int j = m; j >= 1; j --)
			fr[i][j] = min(f[i][j], fr[i][j + 1]);
	}
	memset(g, 0x3f, sizeof(g));
	memset(gl, 0x3f, sizeof(gl));
	memset(gr, 0x3f, sizeof(gr));
	for(int j = 1; j <= m; j ++)
		g[n + 1][j] = gl[n + 1][j] = gr[n + 1][j] = 0;
	for(int i = n; i >= 1; i --)
	{
		for(int j = 1; j <= m; j ++)
			g[i][j] = cost[i][j] + min(gl[i + 1][j - 1], gr[i + 1][j + 1]);
		for(int j = 1; j <= m; j ++)
			gl[i][j] =min(g[i][j], gl[i][j - 1]);
		for(int j = m; j >= 1; j --)
			gr[i][j] =min(g[i][j], gr[i][j + 1]);
	}

\(100pts\)

先枚举颜色\(t\)，将上述做法枚举区间进行优化

代价为\(dpL[l-1][t]+Sum[r][t]-Sum[l-1][t]+dpr[r][t]\)

? $ =(dpL[l-1][t] -Sum[l-1][t])+(Sum[r][t]+dpr[r][t])$ 单调队列优化

设\(A[i] = sum[i][j] + min(gl[i + 1][j - 1], gr[i + 1][j + 1])\ B[i] = min(fl[i - 1][j - 1], fr[i - 1][j + 1]) - sum[i - 1][j]\)

可以单调队列搞一下

	int ans = 1e9;
	for(int j = 1; j <= m; j ++)
	{
		l = 1, r = 0;
		for(int i = 1; i <= n; i ++)
		{
			A[i] = sum[i][j] + min(gl[i + 1][j - 1], gr[i + 1][j + 1]);
			B[i] = min(fl[i - 1][j - 1], fr[i - 1][j + 1]) - sum[i - 1][j];
		}
		for(int i = 1; i <= n; i ++)
		{
			while(l <= r && i - q[l] >= k) l ++;
			while(l <= r && B[q[r]] >= B[i]) r --;
			q[++r] = i;
			ans = min(ans, A[i] + B[q[l]]);
		}
	}

qbxt DAY4 T3

原文：https://www.cnblogs.com/lcezych/p/13847794.html