链接 :
Problem - D - Codeforces
思路 :
划分型dp
设dp[i]表示前i个字母全部染色的最小代价;
用from[]数组来表示最小代价的染色路径 :
当枚举到i时, 要使i染色 , 需要让s中任意一个字符串恰好是t的一个包含(i-1)在内的子串,假设这个s中的字符串为s,开始下标为k,那么dp[i] = min(dp[i] , dp[k] + 1) ;
然后再遍历的过程中记录转换过来的路径即可 ;
代码
// https://codeforces.com/problemset/problem/1714/D
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
typedef long long LL;
typedef pair<int,int> PII ;
const int INF = 1e9 + 10 ;
inline void solve(){
string t ; cin >> t ;
int m = t.size() ;
int n ; cin >> n ;
vector<string> a(n) ; vector<int> l(n);
for(int i=0;i<n;i++) cin >> a[i] , l[i] = a[i].size();
// dp[i]表示前i个字母划分的最小代价
vector<int> dp(m+1,INF) ;
vector<PII> from(m+1) ;
dp[0] = 0 ;
for(int i=1;i<=m;i++){
dp[i] = INF ;
for(int j=0;j<n;j++){
string s = a[j] ;
for(int k=max(0,i-l[j]);k<i&&k<=m-l[j];k++){
if(t.substr(k,l[j])==s && dp[k]+1<dp[i]){// 只需要满足包含i-1在内的一段能够被满足即可
from[i] = {k,j+1} ;
dp[i] = dp[k] + 1 ;
}
}
}
}
if(dp[m]!=INF){
cout << dp[m] << endl ;
int t = m ;
for(;from[t].first>0;t=from[t].first){
cout << from[t].second << " " << from[t].first + 1 << endl ;
}
cout << from[t].second << " " << 1 << endl ;
return ;
}
cout << -1 << endl ;
}
signed main(){
IOS
int _ = 1;
cin >> _;
while(_ --) solve();
return 0;
}