WA#4求解
查看原帖
WA#4求解
566289
RP_INT_MAX楼主2023/3/18 18:03
#include <bits/stdc++.h>
#define pcs putchar(' ')
#define pcn putchar('\n')
#define for1(i,a,b) for(int i=(a);i<=(b);++i)
#define for2(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
namespace IO {
	const int SIZE=(1<<21)+1;
	char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1;
	#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*(iS++))):*(iS++))
	inline void flush() {fwrite(obuf,1,oS-obuf,stdout);oS=obuf;}
	inline void pc(char x) {*oS++=x;if(oS==oT)flush();}
	template<typename Elem>
	void in(Elem &rdnum) {
		rdnum=0;char c=gc();Elem rdflag=1;
		while(c<'0'||c>'9') {if(c=='-')rdflag=-1;c=gc();}
		while(c>='0'&&c<='9') {rdnum=(rdnum<<1)+(rdnum<<3)+(c^48);c=gc();} rdnum*=rdflag;
	}
	template<typename Elem>
	void wtt(Elem wtnum) {if(wtnum<10){pc(wtnum+'0');return;} wtt(wtnum/10);pc(wtnum%10+'0');}
	template<typename Elem>
	void out(Elem wtnum) {if(wtnum<0){pc('-');wtnum=-wtnum;} wtt(wtnum);flush();}
	inline int in_str(char *str) {
	    int len=1;char c;
	    while(!isalpha(c=gc()));str[0]=c;
	    while(isalpha(c=gc()))str[len++]=c;
	    str[len]=0;return len;
	}
} using namespace IO;
const int N=110;
int n,os,a[N],f[N][N][2];
int main () {
	in(n),os=n/2+1;
	for1(i,1,n) in(a[i]),os-=(a[i]&&a[i]&1);
	memset(f,0x70,sizeof f);
	f[0][0][0]=f[0][0][1]=0;
	for1(i,1,n)
		if(a[i]) {
			int o=a[i]&1;
			for1(j,0,min(os,i-1)) f[i][j][o]=min(f[i-1][j][o],f[i-1][j][1-o]+1);
		} else {
			for1(j,1,min(os,i)) f[i][j][1]=min(f[i-1][j-1][1],f[i-1][j-1][0]+1);
			for1(j,0,min(os,i-1)) f[i][j][0]=min(f[i-1][j][1]+1,f[i-1][j][0]);
		}
	out(min(f[n][os][0],f[n][os][1])),pcn;
	return 0;
}
2023/3/18 18:03
加载中...