返回信息流两个01串，从左往右，0和1的个数差不能大于k，并且要求尽量先选第一个串（答案字典序最小）
用dp答案错，有没有什么思路？
[ema1]
http://code.bupt.edu.cn/problem/p/173/
173. 6th K
时间限制 1000 ms 内存限制 65536 KB
题目描述
Alice has a piano which can plays nice music, but it's different from other pianos. It has two rows of keys, and the method of playing it is also quite special. When Alice plays piano, she has to put her two hands on the leftside of the two rows of keys respectively (without touching the leftmost keys of the two rows). And then her hands move on the keys from left to right one by one.
Each time she can move one of her hands by one key, either on the above row or the below row. She has to keep the difference between the number of black keys and white keys she has already touched no more than K to make sure the music is beautiful. When the music is end, her two hands should be both on the rightmost of the piano keyboard. Now Alice wants to know whether she can play nice music, given the description of the piano.
输入格式
There are multiple cases, end by EOF.
For each case, the first line contains two integers and , with two 0-1 strings which are described above.
输出格式
If she can play the music, please output an answer string of length 2N which has the minimum lexicographic order.
In the answer string, “1” represents move on the above row while “2” represents the below row.
If she cannot, just output "Poor Alice".
输入样例
4 1
0011
0110
4 1
1100
1100
输出样例
22121112
Poor Alice
Hint
Take the first sample for explaining:
Suppose Alice puts her left hand on the above row of keys, and right on the below one, the answer string stands for the following process:
1. move right hand to the 1st key of the below row of keys.
2. move right hand to the 2nd key of the below row of keys.
3. move left hand to the 1st key of the above row of keys.
4. move right hand to the 3rd key of the below row of keys.
5. move left hand to the 2nd key of the above row of keys.
6. move left hand to the 3rd key of the above row of keys.
7. move left hand to the 4th key of the above row of keys.
8. move right hand to the 4th key of the below row of keys.
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #89503同步于 2016/4/2
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
kAriOJ 173题 求指教
RainVision
2016/4/2镜像同步8 回复
订阅后，新回复会通过你的通知中心匿名送达。
8 条回复
求教+_+
【 在 Lamperouge 的大作中提到: 】
: 这回是活捉2只了[ema10][ema10]
:
: 【 在 ayzmkk (ayzmkk) 的大作中提到: 】
: : 同求
:
【 在 RainVision 的大作中提到: 】
: 两个01串，从左往右，0和1的个数差不能大于k，并且要求尽量先选第一个串（答案字典序最小）
: 用dp答案错，有没有什么思路？
:
: ...................
flag[i][j]表示第一行前i个字符与第二行前j个字符组合起来差别是否在K内的结果，可以用O（N^2）统计出来，如果flag[i][j]为false，直接不成功。
找路径就是用dfs，先第一行，再第二行这样， 代码很烂，将就看。
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <queue>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;
char up[1003], down[1003];
int N, K;
string ans;
bool dfs(int cur1, int cur2, int delta, string res, vector <vector <bool> > &flag)
{
if (!flag[cur1][cur2])
return false;
if (cur1 == N && cur2 == N) //搜索完成
{
ans = res; //ans为路径结果
return true;
}
if (abs(delta) > K) //一些路径遍历过不成功后，将flag置为false,避免重复搜索
{
flag[cur1][cur2] = false;
return false;
}
if (cur1 < N) //先走第一行的
{
if (dfs(cur1 + 1, cur2, delta + (up[cur1] == '0' ? -1 : 1), res + "1", flag))
return true;
}
if (cur2 < N) //再走第二行的
{
if (dfs(cur1, cur2 + 1, delta + (down[cur2] == '0' ? -1 : 1), res + "2", flag))
return true;
}
flag[cur1][cur2] = false;
return false;
}
int main()
{
while (scanf("%d%d", &N, &K) != EOF)
{
scanf("%s", up);
scanf("%s", down);
ans.clear();
vector <vector <bool> > flag(N + 1, vector <bool> (N + 1, true) );
vector <vector <int> > de(N + 1, vector <int> (N + 1, 0) );
de[0][0] = 0;
for (int i = 1; i <= N; i++)
{
de[i][0] = de[i - 1][0] + (up[i - 1] == '0' ? -1 : 1);
if (abs(de[i][0]) > K)
flag[i][0] = false;
}
for (int j = 1; j <= N; j++)
{
de[0][j] = de[0][j - 1] + (down[j - 1] == '0' ? -1 : 1);
if (abs(de[0][j]) > K)
flag[0][j] = false;
}
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
de[i][j] = de[i - 1][j] + (up[i - 1] == '0' ? -1 : 1);
if (abs(de[i][j]) > K)
flag[i][j] = false;
}
}
string res;
if (!flag[N][N])
{
printf("Poor Alice\n");
continue;
}
if (dfs(0, 0, 0, res, flag))
printf("%s\n", ans.c_str());
else
printf("Poor Alice\n");
}
return 0;
}
多谢，我标记了以后就直接从终点一直贪心，尽量选右手，到起点了，可能这样会存在字典序不是最小。
【 在 wujackjack 的大作中提到: 】
:
: 【 在 RainVision 的大作中提到: 】
: : 两个01串，从左往右，0和1的个数差不能大于k，并且要求尽量先选第一个串（答案字典序最小）
: : 用dp答案错，有没有什么思路？
:
: .........
蟹蟹！
【 在 wujackjack 的大作中提到: 】
:
: 【 在 RainVision 的大作中提到: 】
: : 两个01串，从左往右，0和1的个数差不能大于k，并且要求尽量先选第一个串（答案字典序最小）
: : 用dp答案错，有没有什么思路？
:
: .........