Submission #33608140

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

ll read(){ll r;scanf("%lld",&r);return r;} // read


const int INF = 0x3f3f3f3f;
const int maxc = 'z' - 'a';

vector<int> t;
int f[60][60][60][60]; // [l..r] => a[k][0...i] (prefix(a[k][i]))
int dp[60][60][30]; // [l..r] => char c

int c[60];
vector<int> a[60]; // c[i] -> a[i];
vector<pair<int,int> > c2c; // 单字符映射

int ns,nt;
int K ;

char tmp[60];
int lcStr2VecInt(vector<int> & res){ // lower case string to vector<int>
  scanf("%s", tmp);
  int sz = strlen(tmp);
  res.resize(sz);
  rep(i,0,sz) res[i] = tmp[i] - 'a'; // s 放在 c[0],a[0]
  return sz;
}

void setMin(int &v0,int v1){v0 = min(v0,v1);}

int main(){
  c[0] = maxc + 1; // 不存在的字符
  ns = lcStr2VecInt(a[0]); // s 放在 c[0],a[0]
  nt = lcStr2VecInt(t); // t
  K = read() + 1; // 包含s
  rep(i,1,K){
    scanf("%s", tmp);
    char ch = c[i] = tmp[0] - 'a';
    if(lcStr2VecInt(a[i]) == 1) c2c.push_back({ch, a[i][0]});
  }
  // rep(i,0,K){
  //   printf("c,a : %d -> ",c[i]);
  //   for(auto v:a[i]) printf("%d ",v);
  //   printf("\n");
  // }
  // for(auto [c0,c1]:c2c) printf("c2c:%d -> %d\n",c0,c1);
  rep(l,0,nt) {
    rep(r,l,nt) {
      rep(k,0,K) rep(i,0,50) f[l][r][k][i] = INF;
      rep(c,0,maxc+1) dp[l][r][c] = INF;
    }
    dp[l][l][t[l]] = 0; // 本身就是字符
  }
  // --- init ---
  per(l,0,nt) rep(r,l,nt){ // T[l..r]
    rep(k,0,K){
      int sz = a[k].size();
      rep(i,1,sz){ // T[l..j][j+1..r] = > a[k][0..i-1],a[k][i]
        int &ans = f[l][r][k][i];
        rep(j,l,r) setMin(ans, f[l][j][k][i-1] + dp[j+1][r][a[k][i]]);
        if(i == sz - 1) setMin(dp[l][r][c[k]], ans + 1); // T[i..j] => a[k] => c[k]
      }
    }
    // dp[l][r][c] = min( dp[l][r][k][|a[k]|]) + 1 = min(len > 1(上面算了), len = 1) + 1, len = |a[k]|
    // 26 次 松弛
    rep(c,0,maxc+1) for(auto [c0, c1]: c2c) setMin(dp[l][r][c0], dp[l][r][c1] + 1);
    // 更新 f 中首字母
    rep(k,0,K) setMin(f[l][r][k][0], dp[l][r][a[k][0]]);
  }
  printf("%d\n", f[0][nt-1][0][ns-1] == INF? -1:f[0][nt-1][0][ns-1] );
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:8:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    8 | ll read(){ll r;scanf("%lld",&r);return r;} // read
      |                ~~~~~^~~~~~~~~~~
./Main.cpp: In function ‘int lcStr2VecInt(std::vector<int>&)’:
./Main.cpp:27:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   27 |   scanf("%s", tmp);
      |   ~~~~~^~~~~~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:42:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   42 |     scanf("%s", tmp);
      |     ~~~~~^~~~~~~~~~~

Judge Result