K

题目大意：

给定两个长度为N的01字符串，每一次选取其中的一个依次从左往右读，需要保证已经读过的0和1的个数差小于等于k，试问：这样的读字符串方案是否存在？如果存在，第一个字符串从左往右读一位输出1，第二个字符串从左往右读一位输出2，输出字典序最小的输出方案。

方法1：DFS

这个想法比较自然。首先构造出搜索图map[maxn][maxn]。定义扫描状态(i,j)表示当前第一个字符串扫描到了第i位，第二个字符串扫描到了第j位。(i,j)合法当且仅当当前状态下已经扫描过的01个数差小于等于k。如果(i,j)合法，置map[i][j] = 1；否则map[i][j] = 0。这样就得到了一张由01组成的图。以测试数据

4 1

0011

0110 为例。得到的搜索图map为：

1 1 1 1 1

1 0 1 1 1

0 0 0 1 0

1 0 1 1 1

1 1 1 1 1

现在整个问题转化为找到一条可行的“1”路径，使得一个点能够从图的左上角移动到右下角。注意题目要求字典序最小的输出方案，所以深搜时以“向下”移动优先。

注意深搜的过程。已经回溯过的点肯定不用再走，所以置一个visit矩阵有助于减小搜索量。

/*
sample output:
22121112
Poor Alice
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 1010;
char str1[maxn], str2[maxn], result[2*maxn];
bool map[maxn][maxn];
int cnt1[maxn],cnt2[maxn];
bool visit[maxn][maxn];
int n,k;
bool flag;
void dfs(int u, int v)
{
    if(n == v && n == u)
    {
        flag = true;
        printf("%s\n",result);
        return;
    }
    if(map[u+1][v] == 1 && !visit[u+1][v] && !flag)
    {
        //if(flag) return;
        result[u+v] = '1';
        dfs(u+1,v);
    }
    if(map[u][v+1] == 1 && !visit[u][v+1] && !flag)
    {
        //if(flag) return;
        result[u+v] = '2';
        dfs(u,v+1);
    }
    visit[u][v] =  1;
    if(u==0 && v == 0 && !flag) printf("Poor Alice\n");
    return;
}

int main()
{
    //freopen("test.txt","r",stdin);
    while(scanf("%d%d",&n,&k)!= EOF)
    {
        memset(map,0,sizeof(map));
        scanf("%s%s",str1,str2);
        cnt1[0] = 0;
        cnt2[0] = 0;
        for(int i=0;i<n;++i)
        {
            if(str1[i] == '1')
                cnt1[i+1] = cnt1[i] + 1;
            else cnt1[i+1] = cnt1[i] - 1;
            if(str2[i] == '1')
                cnt2[i+1] = cnt2[i] + 1;
            else cnt2[i+1] = cnt2[i] - 1;
        }
        for(int i=0;i<=n;++i)
            for(int j = 0;j<=n;++j)
            {
                int temp = cnt1[i] + cnt2[j];
                if(abs((double)temp) <= k)
                    map[i][j] = 1;
            }
        result[2*n-1] = '\0';
        /*for(int i=0;i<=n;++i)
        {
            for(int j=0;j<=n;++j)
                cout<<map[i][j]<<' ';
            cout<<endl;
        }*/
        flag = false;
        memset(visit,0,sizeof(visit));
        dfs(0,0);
    }
    return 0;
}

方法二：DP。

令ok[i][j]=1表示从第一个字符串的第i个字符，第二个字符串的第j个字符开始可以扫描完整个字符串。那么可以建立DP递归方程：

ok[i][j-1] = 1 iff ok[i][j] && map[i][j-1]

ok[i-1][j] = 1 iff ok[i][j] && map[i-1][j]

这个方法没有方法一自然，因为逆推不太容易想到。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 1010;
char str1[maxn], str2[maxn];
bool map[maxn][maxn],ok[maxn][maxn];
int cnt1[maxn],cnt2[maxn];
bool visit[maxn][maxn],flag;
int n,k;
int main()
{
    //freopen("test.txt","r",stdin);
    while(scanf("%d%d",&n,&k)!= EOF)
    {
        flag = true;
        memset(map,0,sizeof(map));
        memset(ok,0,sizeof(ok));
        scanf("%s%s",str1,str2);
        cnt1[0] = 0;
        cnt2[0] = 0;
        for(int i=0;i<n;++i)
        {
            if(str1[i] == '1')
                cnt1[i+1] = cnt1[i] + 1;
            else cnt1[i+1] = cnt1[i] - 1;
            if(str2[i] == '1')
                cnt2[i+1] = cnt2[i] + 1;
            else cnt2[i+1] = cnt2[i] - 1;
        }
        for(int i=0;i<=n;++i)
            for(int j = 0;j<=n;++j)
            {
                int temp = cnt1[i] + cnt2[j];
                if(abs((double)temp) <= k)
                    map[i][j] = 1;
            }
        if(!map[n][n])
        {
            printf("Poor Alice\n");
            continue;
        }
        ok[n][n] = 1;
        for(int i = n;i>=0;--i)
            for(int j = n;j>=0;--j)
            {
                if(ok[i][j] && map[i][j-1] && j)
                    ok[i][j-1] = 1;
                if(ok[i][j] && map[i-1][j] && i)
                    ok[i-1][j] = 1;
            }
        if(!(ok[0][1] || ok[1][0]))
            {printf("Poor Alice\n");continue;}
        int i=0,j=0;
        while(i!=n || j!=n)
        {
            if(ok[i+1][j])
            {
                printf("1");
                i++;
            }
            else if(ok[i][j+1])
            {
                printf("2");
                j++;
            }
        }
        printf("\n");

    }
    return 0;
}