3 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef long long ll; int n,a[13][13],len[13],vis[13][13],ck[13][13][13],vs[13]; int dp[13][13][13][13][1111]; int dfs(int i,int l,int j,int r,int s){ if(~dp[i][l][j][r][s])return dp[i][l][j][r][s]; if(s==(1<<n)-1&&l==len[i]&&r==1)return 0; int &now=dp[i][l][j][r][s];now=114514; if(j==n+1){ for(int k=1;k<=n;k++){ now=min(now,dfs(i,l,k,len[k]+1,1<<k-1)); } return now; } if(i<=n&&l<len[i]&&vis[j][a[i][l+1]]<=r)now=min(now,dfs(i,l+1,j,r,s)+1); if(r>1&&vis[i][a[j][r-1]]<=l)now=min(now,dfs(i,l,j,r-1,s)+1); if(i<=n&&l<len[i]&&r>1&&a[i][l+1]==a[j][r-1])now=min(now,dfs(i,l+1,j,r-1,s)+1); for(int k=1;k<=n;k++)if(!((s>>k-1)&1)&&(i==n+1||((vs[k]&vs[i])==vs[k]&&ck[i][k][l+1])))now=min(now,dfs(k,0,j,r,s|(1<<k-1))); if(r==1){ for(int k=1;k<=n;k++)if(!((s>>k-1)&1))for(int ll=1;ll<=len[k]+1;ll++)if((vs[j]&vs[k])==vs[j]&&ck[k][j][ll])now=min(now,dfs(i,l,k,ll,s|(1<<k-1))); } return now; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1;i<=n;i++)for(int j=0;j<10;j++)vis[i][j]=114514; for(int i=1;i<=n;i++){ int x; while(cin>>x&&x){ len[i]++;a[i][len[i]]=x;vis[i][x]=len[i];vs[i]|=1<<x-1; } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=len[i];k++){ int l=k; for(int r=1;r<=len[j];r++){ if(a[i][l]==a[j][r])l++; if(l>len[i]){ ck[i][j][k]=1; break; } } } ck[i][j][len[i]+1]=1; } } memset(dp,-1,sizeof(dp)); int ans=dfs(n+1,0,n+1,n+2,0); if(ans<200)cout<<ans; else cout<<-1; return 0; } -
0
/** * loj * Problem#6037 * Accepted * Time: 1224ms * Memory: 25208k */ #include <iostream> #include <cstdlib> #include <cstdio> #include <set> using namespace std; typedef bool boolean; const int N = 11; const int Lim = 1 << 10; #define last_one(__x) (__builtin_ffs(__x) - 1) int n; int len[N]; int s[N][N]; int exi[N][N]; int can[N][N]; // L: forward, R: backward int usable[N][N]; int f[N][N][N][N][1024]; inline void init() { scanf("%d", &n); set<int> ss; for (int i = 0, x; i < n; i++) { int l = 0, hash_val = 0; while (~scanf("%d", &x) && x) { s[i][l++] = x; hash_val = hash_val * 10 + x; } len[i] = l, s[i][l] = 0; if (ss.count(hash_val)) n--, i--; else ss.insert(hash_val); } for (int i = 0; i < n; i++) for (int j = 0; j < len[i]; j++) exi[i][j + 1] = exi[i][j] | (1 << s[i][j]); } // start at pos boolean check(int a, int pos, int b) { int *pa = s[a] + pos, *pb = s[b]; while (*pa || *pb) { if (*pa == *pb) pa++, pb++; else if ((1 << *pb) & exi[a][pa - s[a]]) pb++; else return false; } return true; } void upd(int& a, int b) { if (a > b) a = b; } // considering s[L][pl], s[R][pr - 1], S remained int dp(int L, int pl, int R, int pr, int S) { if (!S && pl == len[L] && !pr) return 0; int &rt = f[L][pl][R][pr][S]; if (rt) return rt; rt = Lim; for (int T = S & can[L][pl], i = last_one(T); T; T -= (T & (-T)), i = last_one(T)) upd(rt, dp(i, 0, R, pr, S ^ (1 << i))); if (!pr) { for (int i = 0; i < n && (S >> i); i++) if ((S >> i) & 1) // for (int j = 0; j <= len[i]; j++) // if ((can[i][j] >> R) & 1) // upd(rt, dp(L, pl, i, j, S ^ (1 << i))); for (int T = usable[R][i], j = last_one(T); T; T -= (T & (-T)), j = last_one(T)) upd(rt, dp(L, pl, i, j, S ^ (1 << i))); } if (pl < len[L] || pr) { int vl = s[L][pl], vr = ((pr) ? (s[R][pr - 1]) : (0)); if (vl == vr) upd(rt, dp(L, pl + 1, R, pr - 1, S) + 1); // if (pl < len[L] && _exi[R][pr] & (1 << vl)) if (pl < len[L] && exi[R][pr] & (1 << vl)) upd(rt, dp(L, pl + 1, R, pr, S) + 1); if (pr && exi[L][pl] & (1 << vr)) upd(rt, dp(L, pl, R, pr - 1, S) + 1); } // cerr << L << " " << pl << " " << R << " " << pr << " " << S << " " << rt << '\n'; return rt; } inline void solve() { // forward for (int idx = 0; idx < n; idx++) { for (int pos = 0; pos <= len[idx]; pos++) { for (int ano = 0; ano < n; ano++) { if (ano ^ idx) can[idx][pos] |= check(idx, pos, ano) << ano; } // cerr << can[idx][pos] << ' '; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i ^ j) { for (int pos = 0; pos <= len[j]; pos++) if ((can[j][pos] >> i) & 1) usable[i][j] |= (1 << pos); } } } len[n] = 0; for (int i = 0; i < N; i++) { exi[n][i] = 2046; //_exi[n][i] = 2046; can[n][i] = 2047; } int all = (1 << n) - 1, ans = Lim; // ans = dp(n, 0, 1, len[1], all ^ 2); for (int i = 0; i < n; i++) { upd(ans, dp(n, 0, i, len[i], all ^ (1 << i))); } if (ans == Lim) puts("-1"); else printf("%d\n", ans); } int main() { init(); solve(); return 0; } -
0
#include<bits/stdc++.h> using namespace std; const int N=11; int n,a[N][N],b[N][N][N],vs[N],vis[N][N],len[N],dp[1<<10][N][N][N][N]; bool v[1<<10][N][N][N][N]; inline int dfs(int s,int i,int l,int j,int r){ if(v[s][i][l][j][r]) return dp[s][i][l][j][r]; if(s==(1<<n)-1&&l==len[i]&&r==1) return 0; int &re=dp[s][i][l][j][r];re=1e9,v[s][i][l][j][r]=1; if(!s){ for(int k=0;k<n;k++) re=min(re,dfs(1<<k,i,l,k,len[k]+1)); return re; }if(l<len[i]&&vis[j][a[i][l+1]]<=r) re=min(re,dfs(s,i,l+1,j,r)+1); if(r>1&&vis[i][a[j][r-1]]<=l) re=min(re,dfs(s,i,l,j,r-1)+1); if(a[i][l+1]==a[j][r-1]&&i<n&&j<n&&l<len[i]&&r>1) re=min(re,dfs(s,i,l+1,j,r-1)+1); for(int k=0;k<n;k++) if(!(s&(1<<k))&&(b[i][k][l+1]==1||i==n)) if(((vs[k]&vs[i])==vs[k])||i==n) re=min(re,dfs(s|(1<<k),k,0,j,r)); if(r==1) for(int k=0;k<n;k++) if(!(s&(1<<k))&&(vs[j]&vs[k])==vs[j]) for(int p=1;p<=len[k]+1;p++) if(b[k][j][p]) re=min(re,dfs(s|(1<<k),i,l,k,p)); return re; }signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0),cin>>n; for(int i=0;i<n;i++) for(int j=1;j<10;j++) vis[i][j]=1e9; for(int i=0,cc;i<n;i++) while(cin>>cc){ if(!cc) break;a[i][++len[i]]=cc,vis[i][cc]=len[i],vs[i]|=(1<<cc); }for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i!=j){ for(int k=1;k<=len[i];k++){ for(int l=k,r=1;r<=len[j];r++){ if(a[i][l]==a[j][r]) l++; if(l>len[i]){b[i][j][k]=1;break;} } }b[i][j][len[i]+1]=1; }int ans=dfs(0,n,0,n,1); return cout<<(ans<200?ans:-1),0; }
Benny
LV 10
MOD
@ 2026-8-13 10:32:38
- 1