比赛 |
至少完成十道练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
美丽的感觉 |
最终得分 |
100 |
用户昵称 |
Emine |
运行时间 |
0.004 s |
代码语言 |
C++ |
内存使用 |
1.29 MiB |
提交时间 |
2017-05-23 19:32:03 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
bool dp[maxn][maxn];
char a[maxn],b[maxn];
int n;
bool dfs(int x,int y){
if(!x&&!y) return 1;
if(!dp[x][y]) dp[x][y]=1; //记忆化:走过一遍 false,没走的话做标记 true;
else return 0;
/*
三种情况
*/
if((x-2)>=0&&a[x-1]!=a[x]&&dfs(x-2,y)) //1.从左边那一堆取两张
return 1;
if((y-2)>=0&&b[y-1]!=b[y]&&dfs(x,y-2)) //2.从右边那一堆取两张
return 1;
if((y-1)>=0&&(x-1)>=0&&a[x]!=b[y]&&dfs(x-1,y-1)) //3.左右堆各取一张
return 1;
return 0;
}
int main(){
freopen("card_.in","r",stdin);
freopen("card_.out","w",stdout);
scanf("%d",&n);
scanf("%s%s",a+1,b+1);
if(!dfs(n,n)) printf("Impossible!\n");
else printf("Accepted!\n");
return 0;
}