题意：
给出n个字符的01编码串，用这些串组成尽可能短的会有冲突的编码串
例：
3个编码串0 01 10，有冲突的最短的是010
问题相当于用给定的01串，组合成最短的2个一样的串
对于两个有冲突的编码串，它在形成过程中的有效状态只有目前最后一个串的最后没有匹配的部分
令d[i][j]表示第i个字符串，还有最后j位没有匹配
然后可以用堆优化的迪杰斯特拉算法进行状态转移
当从优先队列中取出j=0的状态时，输出当前总长度
#include<queue> #include<cstdio> #include<cstring> #include<iostream> using namespace std; #define N 1001 #define M 17 string s[N]; int len[N],num[N]; int d[N][M]; int bit[M]; struct node { int id,re,dis; bool operator < (node p) const { return dis>p.dis; } }; priority_queue<node>q; int main() { int n; scanf("%d",&n); node now,nxt; for(int i=1;i<=n;++i) for(int j=0;j<=16;++j) d[i][j]=1e9; for(int i=1;i<=n;++i) { cin>>s[i]; len[i]=s[i].length(); for(int j=0;j<len[i];++j) num[i]=num[i]*2+(s[i][j]-‘0‘); now.id=i; now.re=len[i]; now.dis=0; q.push(now); } bit[1]=2; for(int i=2;i<=16;++i) bit[i]=bit[i-1]<<1; for(int i=1;i<=16;++i) --bit[i]; while(!q.empty()) { now=q.top(); if(!now.re) { printf("%d",now.dis); return 0; } q.pop(); for(int i=1;i<=n;++i) { if(now.id==i && now.re==len[i]) continue; if(len[i]<=now.re) { if((num[now.id]>>(now.re-len[i])&bit[len[i]])==num[i]) { nxt.id=now.id; nxt.re=now.re-len[i]; nxt.dis=now.dis+len[i]; if(nxt.dis<d[nxt.id][nxt.re]) { q.push(nxt); d[nxt.id][nxt.re]=nxt.dis; } } } else { if((num[i]>>(len[i]-now.re)&bit[now.re])==(num[now.id]&bit[now.re])) { nxt.id=i; nxt.re=len[i]-now.re; nxt.dis=now.dis+now.re; if(nxt.dis<d[nxt.id][nxt.re]) { q.push(nxt); d[nxt.id][nxt.re]=nxt.dis; } } } } } printf("0"); }
ICPC Yokohama 2019 G Ambiguous Encoding
原文：https://www.cnblogs.com/TheRoadToTheGold/p/13673179.html