CF-517B-DP

http://codeforces.com/contest/1072/problem/B

给出两个数列 a,b 长度为n-1 ,询问是否能构造出一个长度为n的数列t，使得 所有的ab都满足  a[i]=t[i]|t[i+1]  b[i]=t[i]&t[i+1]   ，其中所有数列的值都满足 [0,3]之内。

由于数值只有四种，直接dp，f[i][j]表示t[i]=j是否可行，记录下路径就好了。

#include<iostream>
#include<cstring>
#include<cstdio> 
using namespace std;
#define LL long long 
const int maxn=100000+15;
int n,a[maxn],b[maxn];
bool f[maxn][4];
int pre[maxn][4];
void out(int n,int i){
    if(n==0) return;
    out(n-1,pre[n][i]);
    cout<<i<<' ';
}
int main(){
    cin>>n;
    for(int i=1;i<n;++i) cin>>a[i];
    for(int i=1;i<n;++i) cin>>b[i];
    memset(pre,-1,sizeof(pre));
    f[1][0]=f[1][1]=f[1][2]=f[1][3]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<4;++j){
            if(f[i][j]){
                for(int k=0;k<4;++k){
                    if((j|k)==a[i] && (j&k)==b[i]){
                        f[i+1][k]=1;
                        pre[i+1][k]=j;
                    }
                }
            }
        }
    }
    for(int i=0;i<4;++i){
        if(f[n][i]){
            puts("YES");
            out(n-1,pre[n][i]);
            cout<<i<<endl;
            return 0;
        }
    }
    puts("NO");
    return 0;
}