[cf] Educational Codeforces Round 128 (Rated for Div. 2) E状态机dp

前言

传送门 :

题意 : 给定一个 2 ∗ n 2*n 2∗n的只包括 ∗ . *. ∗.的矩阵,询问将所有 ∗ * ∗合并为一个的最小代价

思路 : 赛时没思路,赛后发现是 d p dp dp

状态表示 : f [ i ] [ 0 / 1 ] f[i][0/1] f[i][0/1] 表示 当前这一列向上 和 向下合并

状态计算 :

• g [ i ] [ 0 ] = = ∗ g[i][0]= = * g[i][0]==∗ f [ i ] [ 1 ] = m i n ( f [ i − 1 ] [ 0 ] , f [ i − 1 ] [ 1 ] ) + 2 f[i][1]=min(f[i-1][0],f[i-1][1])+2 f[i][1]=min(f[i−1][0],f[i−1][1])+2 因为第一格子也有 ∗ * ∗,因此不仅需要从左边向右移动一位同时还需要将上面的往下合并因此需要 2 2 2代价
• g [ i ] [ 0 ] ≠ ∗ g[i][0]\neq* g[i][0]​=∗ f [ i ] [ 1 ] = m i n ( f [ i − 1 ] [ 0 ] + 1 , f [ i − 1 ] [ 1 ] ) + 1 f[i][1]=min(f[i-1][0]+1,f[i-1][1])+1 f[i][1]=min(f[i−1][0]+1,f[i−1][1])+1 显然的前面的向上合并需要先向下移动然后同时再向右移动

另外的计算方式同理

code :

char s1[N],s2[N];

int f[N][2];

void solve(){
	int n,L,R;
	cin>>n>>s1+1>>s2+1;
	
	for(int i=1;is2+1;

	for(int i=1;i