比赛 至少完成十道练习 评测结果 AAAAAAAAAA
题目名称 美丽的感觉 最终得分 100
用户昵称 Mealy 运行时间 0.016 s
代码语言 C++ 内存使用 96.04 MiB
提交时间 2017-05-23 20:04:25
显示代码纯文本
//2598
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <cmath>

const int nmax = 10010;

using namespace std;

int N;

char Sa[nmax] = {0};
char Sb[nmax] = {0};

int Ba[nmax] = {0};
int Bb[nmax] = {0};

int Ra[nmax] = {0};
int Rb[nmax] = {0};

bool F[nmax][nmax] = {0};

void PreDo(){
	scanf("%d",&N);
	scanf("%s%s",Sa + 1,Sb + 1);
	
	Ba[0] = 0;
	Ra[0] = 0;
	for(int i = 1;i <= N;i++){
		Ra[i] = Ra[i-1];
		Ba[i] = Ba[i-1];
		Sa[i] == '0' ? Ra[i]++ : Ba[i]++;
	}
	
	Bb[0] = 0;
	Rb[0] = 0;
	for(int i = 1;i <= N;i++){
		Rb[i] = Rb[i-1];
		Bb[i] = Bb[i-1];
		Sb[i] == '0' ? Rb[i]++ : Bb[i]++;
	}
}

bool Check(int x, int y){
	if(x==0&&y==0){
		return 0;
	}
	else{
		if(F[x-1][y]||F[x][y-1]){
			return 1;
		}	
	}
	return 0;
}


void DP(){
	/*
	for(int i=1;i<=N;i++){
		printf("%d %d\n",Rb[i],Bb[i]);
	}
	*/
	F[0][0] = 1;
	for(int i = 0;i <= N;i++){
		for(int j = 0;j <= N;j++){
			if(Check(i, j)){
				if(abs(Ra[i] + Rb[j] - Ba[i] - Bb[j]) <= 1){
					F[i][j] = 1;
				}
			}
		}
	}
	/*
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			printf("%d ",F[i][j]);
		}
		printf("\n");
	}
	*/
	F[N][N]==1 ? printf("Accepted!\n") : printf("Impossible!\n");
}

int main(){
	freopen("card_.in","r",stdin);
	freopen("card_.out","w",stdout);
	PreDo();
	DP();
	return 0;
}