ARC109F - 1D Kingdom Builder

一行格子，其中小于\(0\)的格子为白色，大于\(n\)的格子为黑色，中间的格子颜色由题目给出。

有一些格子需要被标记。标记按照以下规则进行：选择一个颜色\(c\)，找到一个未标记的旁边有标记点的颜色为\(c\)的格子，在这个格子上标记；如果找不到这样的格子，就找任意一个颜色为\(c\)的格子。

问标记完所有需要被标记的点，最少要操作多少次。

\(n\le 10^5\)

%%%gmh,dyp早就切了

想题的时候先想出假做法，写个\(O(n^2)\)的暴力交上去发现WA了，后来另外想到了正解的结论。当时不会证充分性就瞄了瞄题解，确认后自己证了下才开打。当然做法是自己的，所以可以很高兴地认为自己做出了一半。

很奇怪别人的做法都要设那么多状态显得特别阴间。

可以考虑：对于一个终止状态，如何判定它是可以得到的。

对于一个连续段，显然只要一个点被标记整个连续段都可以被标记；那问题转化成了：是否可以在每个连续段都至少标记一个点。

先特殊计算只有一个连续段的情况。

为了方便表示将题目中的两种情况称为操作一和操作二。显然一个连续段从被标记必须通过一次操作二。

第一次操作后，连续段相邻的两个位置的颜色都不能使用操作二；因为后面还有连续段所以必须要只有一种颜色的操作二被禁止了。类似地考虑，除了最后一个连续段，其它连续段操作之后都要保证存在一种颜色没有被禁止，而且后面的连续段都要包含这种颜色。

称这个没有被禁止操作二的颜色为\(c\)（记被禁止的颜色为\(\overline c\)）。将以上的分析整理一下得：

中间的连续段算上相邻两格一定包含子序列\(\overline c c\overline c\)。
第一个连续段算上相邻两格一定包含子序列\(\overline c \overline c\)。
最后一个连续段一定包含子序列\(c\)。

于是就可以DP了。

DP方式多样，这里是阳间的：先题目的序列前后各自加两位。设\(f_{i,0/1,0/1}\)表示\(i\)不选，是否出现第一个连续段，是否出现最后一个连续段。转移分三种情况从\(f_j\)转移到\(f_i\)。可以维护每种情况的合法的最优\(f_j\)，记多几个变量辅助转移。对于每种转移，显然能转移到\(i\)的是一段前缀，并且\(i\)增加时前缀伸长，于是可以预处理能转移到\(i\)的前缀的位置（子序列自动机即可）。时间就是\(O(n)\)的。

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 100007

#define INF 0x7f7f7f7f

int n;

int s[N],t[N];

int ps[N][2];

int _pre[N][2];

int pre(int x,int c){return x<0?-1:_pre[x][c];}

void init(){

	static char str[N];

	scanf("%d%s",&n,str+1);

	for (int i=1;i<=n;++i) s[i+1]=(str[i]=='b'?1:0);

	scanf("%s",str+1);

	for (int i=1;i<=n;++i) t[i+1]=(str[i]=='o'?1:0);

	n+=3;

	s[1]=0,s[n-1]=s[n]=1;

	t[1]=t[n-1]=t[n]=0;

	_pre[0][0]=_pre[0][1]=-1;

	for (int i=1;i<=n+1;++i){

		_pre[i][0]=(s[i-1]==0?i-1:_pre[i-1][0]);

		_pre[i][1]=(s[i-1]==1?i-1:_pre[i-1][1]);

	}

}

int ans;

int dp[N][2][2];

int rf[N],rl[N],rn[N];

int fir[2],lst[2],nor[2][2];

void upd(int &x,int y){x>y?x=y:0;}

int work(int c){

	int _c=c^1;

	for (int i=1;i<=n;++i){

		rf[i]=pre(pre(i+1,_c)-1,_c);

		rl[i]=pre(i,c)-1;

		rn[i]=pre(pre(pre(i+1,_c),c),_c);

	}

	memset(dp,127,sizeof dp);

	memset(fir,127,sizeof fir);

	memset(lst,127,sizeof lst);

	memset(nor,127,sizeof nor);

	dp[0][0][0]=0;

	int pf=0,pl=0,pn=0;

	for (int i=1;i<=n;++i){

		if (t[i])

			continue;

		for (;pf<=rf[i];++pf){

			upd(fir[0],dp[pf][0][0]-pf);

			upd(fir[1],dp[pf][0][1]-pf);

		}

		for (;pl<=rl[i];++pl){

			upd(lst[0],dp[pl][0][0]-pl);

			upd(lst[1],dp[pl][1][0]-pl);

		}

		for (;pn<=rn[i];++pn){

			upd(nor[0][0],dp[pn][0][0]-pn);

			upd(nor[1][0],dp[pn][1][0]-pn);

			upd(nor[0][1],dp[pn][0][1]-pn);

			upd(nor[1][1],dp[pn][1][1]-pn);

		}

		memcpy(dp[i],dp[i-1],sizeof dp[i]);

		upd(dp[i][0][0],nor[0][0]+i-1);

		upd(dp[i][1][0],min(nor[1][0],fir[0])+i-1);

		upd(dp[i][0][1],min(nor[0][1],lst[0])+i-1);

		upd(dp[i][1][1],min(nor[1][1],min(fir[1],lst[1]))+i-1);

	}

	return dp[n][1][1];

}

int main(){

	init();

	int mn=n,mx=1;

	for (int i=1;i<=n;++i)

		if (t[i]==1){

			mn=min(mn,i);

			mx=max(mx,i);

		}

	ans=mx-mn+1;

	ans=min(ans,work(0));

	ans=min(ans,work(1));

	printf("%d\n",ans);

	return 0;

}

巴特西

ARC109F - 1D Kingdom Builder

最新文章

热门文章