题目链接：点击查看
题目大意：根据最长公共子序列抛出一个新定义，“ 最短非公共子序列 ”，假设给定了字符串 s1 和 s2，设 s 为 s1 和 s2 的“最短非公共子序列”，那么 s 需要满足：
s 不是 s1 的子序列s 不是 s2 的子序列满足上述两个条件下，s 尽可能短现在给出两个 01 串，输出其“最短非公共子序列”，如果有多个答案，输出字典序最小的
题目分析：动态规划问题，因为题目中存在着字典序最小的这个限制，此类问题可以参考：CodeForces - 1341D
所以可以反向去寻找可行解，然后正向贪心输出即可，既然是需要反向转移，那么根据最长公共子序列的状态设置 dp[ i ][ j ] 为：s1[ i ] ~ s[ len1 ] 和 s2[ j ][ len2 ] 的这两个后缀中的 “ 最短非公共子序列 ”，转移的话也比较简单，在 s1 中到达了 s1[ i ]，在 s2 中到达了 s2[ j ]，此时分两种情况讨论：
假设下一位需要放置 0，那么需要在 s1 和 s2 中再找到一个 0，即需要在 s1 中找到 i 位置后的第一个 0，在 s2 中找到 j 位置后的第一个 0，设 s1[ ii ] 和 s2[ jj ] 为满足条件的两个位置，那么有 dp[ i ][ j ] = min( dp[ i ][ j ] , dp[ ii ][ jj ] + 1 )假设下一位需要放置 1，那么需要在 s1 和 s2 中再找到一个 1，处理方法同上如此转移就好了，转移的过程中记录一下路径，最后正向贪心扫一遍就是答案了
代码：
//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> using namespace std; typedef long long LL; typedef unsigned long long ull; const int inf=0x3f3f3f3f; const int N=4e3+100; char s1[N],s2[N]; int nt1[N][2],nt2[N][2],len1,len2; int dp[N][N],path[N][N]; int dfs(int x,int y) { if(x==len1+1&&y==len2+1) return dp[x][y]=0; if(dp[x][y]!=-1) return dp[x][y]; int ans1=dfs(nt1[x][0],nt2[y][0]);//选0 int ans2=dfs(nt1[x][1],nt2[y][1]);//选1 if(ans1<=ans2) path[x][y]=0; else path[x][y]=1; return dp[x][y]=min(ans1,ans2)+1; } void print(int x,int y) { if(x==len1+1&&y==len2+1) return; putchar(path[x][y]+'0'); print(nt1[x][path[x][y]],nt2[y][path[x][y]]); } void init(char s[],int &len,int nt[][2]) { len=strlen(s+1); nt[len+1][0]=nt[len+1][1]=len+1; nt[len][0]=nt[len][1]=len+1; for(int i=len-1;i>=0;i--) { nt[i][0]=nt[i+1][0]; nt[i][1]=nt[i+1][1]; nt[i][s[i+1]-'0']=i+1; } } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.ans.txt","w",stdout); #endif // ios::sync_with_stdio(false); scanf("%s%s",s1+1,s2+1); init(s1,len1,nt1); init(s2,len2,nt2); memset(dp,-1,sizeof(dp)); dfs(0,0); print(0,0); return 0; }
