记忆化搜索(DFS+DP) URAL 1501 Sense of Beauty
2024-09-30 10:09:48
/*
题意:给了两堆牌,每次从首部取出一张牌,按颜色分配到两个新堆,分配过程两新堆的总数差不大于1
记忆化搜索(DFS+DP):我们思考如果我们将连续的两个操作看成一个集体操作,那么这个操作必然是1红1黑
考虑三种情况:a[]连续两个颜色相同,输出11;b[]连续两个相同,输出22;
a[x] != b[y], 输出12;否则Impossible
详细解释:http://blog.csdn.net/jsun_moon/article/details/10254417
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
using namespace std; const int MAXN = 1e3 + ;
const int INF = 0x3f3f3f3f;
char a[MAXN], b[MAXN];
bool dp[MAXN][MAXN]; bool DFS(int x, int y)
{
if (!x && !y) return true;
if (!dp[x][y]) dp[x][y] = true;
else return false; if ((x-)>= && a[x] != a[x-] && DFS (x-, y))
{
printf (""); return true;
}
if ((y-)>= && b[y] != b[y-] && DFS (x, y-))
{
printf (""); return true;
}
if ((x-)>= && (y-)>= && a[x] != b[y] && DFS (x-, y-))
{
printf (""); return true;
} return false;
} int main(void) //URAL 1501 Sense of Beauty
{
//freopen ("V.in", "r", stdin); int n;
while (scanf ("%d", &n) == )
{
memset (dp, false, sizeof (dp));
scanf ("%s", a+); scanf ("%s", b+); if (!DFS (n, n)) puts ("Impossible");
else puts ("");
} return ;
} /*
Impossible
*/
最新文章
- Node学习笔记(三):基于socket.io web版你画我猜(二)
- 不是技术牛人,如何拿到国内IT巨头的Offer(转载)
- ORA-01078、ORA-01565、ORA-17503、ORA-29701
- poj 2104 K-th Number(主席树)
- Azure PowerShell (二)云服务
- jar包和war包的区别:
- .NET c# 串口通信
- 怎样在超级终端和PC之间通过串口传输文件
- HDU更多的学校比赛9场 HDU 4965Fast Matrix Calculation【矩阵运算+数学技巧】
- 团队作业8——第二次项目冲刺(Beta阶段)--5.21 second day
- maven 每次update后影响接口实现类的问题
- AR8033 1000M模式下ping包丢包率过大分析与解决
- CSS图形
- ASP.NET Core 登录失败。该登录名来自不受信任的域,不能与集成身份验证一起使用。
- 编程六月定律 | 外刊IT评论网
- 【Codeforces528D】Fuzzy Search FFT
- 20162314 Sortingtest-work after class
- Linux---more命令学习
- MVVM、MVC框架的认识
- Vue生命周期各阶段发生的事情
热门文章
- C#高阶与初心:(二)P/Invoke平台调用
- monitor and move the log content to our big data system
- Statelessness Provide credentials with the request. Each request MUST stand alone and should not be affected from previous conversation happened from same client in past.
- createDocumentFragment 文档碎片提升dom增删的性能
- iOS 开发用到的常用工具
- [原创]java调用PageOffice生成word
- codeforces 696C C. PLEASE(概率+快速幂)
- MYSQL数据库学习----MYSQL数据类型
- spring+mybatis 多数据源整合--temp
- 网易蜂巢(云计算基础服务)MongoDB服务重磅来袭