updata on 2020.3.19

往博客园搬的时候看了看自己以前写的blog

其实没多久，才两个多月，感觉自己之前写的东西好罗嗦啊。。

但也是最近写的blog才开始多起来

当然现在也没好到哪去。。。

CF1286A题解

整理博客的时候改了一下分类标签，重新审核一下

dp

觉得这题作为一个C比div2的B要简单点吧，算是找回点dp的信心。。。

首先可以想到，只需关心每个数的奇偶，具体是几不用记录

所以\(0\)表示偶数，\(1\)表示奇数，\(-1\)表示不确定，存在\(a[]\)中

\(num[0/1]\)表示一共有几个偶/奇数需要填

状态：

\(f[i][o][j][0/1]\): 考虑前\(i\)位，还剩\(o\)个偶数能用，剩\(j\)个奇数能用，第\(i\)位填的是偶数/奇数

初始：

先都设为极大值

第一位填好了：\(f[1][num[0]][num[1]][a[1]]=0\)
第一位需要自己填： \(f[1][num[0]-1][num[1]][0]=f[1][num[0]][num[1]-1][1]=0\)，要判断\(num[0]\)和\(num[1]\)是否大于0

转移：

\(i\)位填好了：

直接判断与前一位是否相等，不相等就加一

\(f[i][o][j][a[i]]=\min(f[i][o][j][a[i]],f[i-1][o][j][1]+(a[i] \neq 1))\)

\(f[i][o][j][a[i]]=\min(f[i][o][j][a[i]],f[i-1][o][j][0]+(a[i] \neq 0))\)
\(i\)位需要自己填：

分别处理\(i\)位是偶数/奇数，在对应\(i-1\)位是偶数/奇数，共四种。

容易想出\(i\)位是偶数/奇数时，被转移的状态分别应该\(o+1\)/\(j+1\)(因为记录的是可以可以填进去的偶数/奇数还剩几个，用了一个，当然要从剩余数多一个的状态转移而来）

\(f[i][o][j][1]=\min(f[i][o][j][1],f[i-1][o][j+1][1])\)

\(f[i][o][j][1]=\min(f[i][o][j][1],f[i-1][o][j+1][0]+1)\)

\(f[i][o][j][0]=\min(f[i][o][j][0],f[i-1][o+1][j][0])\)

\(f[i][o][j][0]=\min(f[i][o][j][0],f[i-1][o+1][j][1]+1)\)

答案：

当然是\(\min(f[n][0][0][1],f[n][0][0][0])\)

其实代码中好多取\(\min\)是不需要的，但是为了方便就都写上了懒得想

另外状态可能还能再优化？欢迎评论区指出

\(code.\),复杂度\(O(n^3)\)

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<iomanip>

#include<cstring>

#define R register

#define EN printf("\n")

#define LL long long

inline int read(){

	int x=0,y=1;

	char c=std::getchar();

	while(c<'0'||c>'9'){if(c=='-') y=-1;c=std::getchar();}

	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}

	return x*y;

}

int n;

int f[106][106][106][2];

int a[106],num[2];

inline void min(int &x,int y){(x>y)&&(x=y);}

int main(){

	n=read();

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

		a[i]=read();

		if(!a[i]){a[i]=-1;continue;}

		a[i]&=1;

		num[a[i]]++;

	}

	num[1]=(n&1?n/2+1:n/2)-num[1];num[0]=n/2-num[0];

	std::memset(f,0x3f,sizeof f);

	if(a[1]==-1){

		if(num[0]>0) f[1][num[0]-1][num[1]][0]=0;

		if(num[1]>0) f[1][num[0]][num[1]-1][1]=0;

	}

	else if(a[1]) f[1][num[0]][num[1]][1]=0;

	else f[1][num[0]][num[1]][0]=0;

	for(R int i=2;i<=n;i++){

		if(a[i]!=-1){

			for(R int o=num[0];o>=0;o--){

				for(R int j=num[1];j>=0;j--)

					min(f[i][o][j][a[i]],f[i-1][o][j][1]+(a[i]!=1)),

					min(f[i][o][j][a[i]],f[i-1][o][j][0]+(a[i]!=0));

			}

			continue;

		}

		for(R int o=num[0];o>=0;o--){

			for(R int j=num[1];j>=0;j--){

				min(f[i][o][j][1],f[i-1][o][j+1][1]);

				min(f[i][o][j][1],f[i-1][o][j+1][0]+1);

				min(f[i][o][j][0],f[i-1][o+1][j][0]);

				min(f[i][o][j][0],f[i-1][o+1][j][1]+1);

			}

		}

	}

	std::printf("%d",std::min(f[n][0][0][1],f[n][0][0][0]));

	return 0;

}

巴特西

题解 CF1286A 【Garland】

CF1286A题解

状态：

初始：

转移：

答案：

最新文章

热门文章