fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 1e2 + 5;  
  11. const int M = 1e2 + 5;  
  12.  
  13. template<typename T>
  14. bool minimize(T& a, const T& b) {
  15. 	if (a < b) return false;
  16. 	a = b; 
  17. 	return true; 
  18. }
  19.  
  20. int n, m; 
  21. string T;  
  22. vector<string> S[N]; 
  23. int dp[N][M]; // dp[i][j] = số tiền ít nhất cần dùng khi xét i bags đầu tiên, và trùng được đến vị trí thứ j của xâu T
  24.  
  25. bool matched(const string& T, int j, const string& S) {
  26. 	if (j + S.size() > m) return false;  
  27. 	for (int i = 0; i < S.size(); i++) {
  28. 		if (T[j + 1 + i] != S[i]) return false;
  29. 	}
  30. 	return true; 
  31. }
  32.  
  33. int main() {
  34. 	ios::sync_with_stdio(0); cin.tie(0);  	
  35. 	cin >> T; 
  36. 	m = T.size(); 
  37. 	T = ' ' + T;  
  38.  
  39. 	cin >> n;   
  40. 	for (int i = 1; i <= n; i++) {
  41. 		int a; cin >> a;   
  42. 		S[i].resize(a); 
  43. 		for (int j = 0; j < a; j++) {
  44. 			cin >> S[i][j];  
  45. 		}
  46. 	}
  47.  
  48. 	for (int i = 0; i <= n; i++) {
  49. 		for (int j = 0; j <= m; j++) dp[i][j] = INF;  
  50. 	}	
  51.  
  52. 	dp[0][0] = 0;  
  53.  
  54. 	for (int i = 0; i < n; i++) {
  55. 		for (int j = 0; j <= m; j++) {
  56. 			if (dp[i][j] == INF) continue; 
  57.  
  58. 			// không quan tâm túi thứ i 
  59. 			minimize(dp[i + 1][j], dp[i][j]);  
  60.  
  61. 			// chọn một xâu từ túi thứ i 
  62. 			for (auto& s : S[i + 1]) {
  63. 				if (!matched(T, j, s)) continue; 
  64. 				minimize(dp[i + 1][j + s.size()], dp[i][j] + 1); 
  65. 			}
  66. 		}
  67. 	}
  68.  
  69. 	int ans = dp[n][m]; 
  70. 	if (ans == INF) ans = -1;  
  71.  
  72. 	cout << ans << '\n'; 
  73. }
  74.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
aaabbbbcccc
6
2 aa aaa
2 dd ddd
2 ab aabb
4 bbaa bbbc bbb bbcc
2 cc bcc
3 ccc cccc ccccc
stdout
copy 
4
https://ideone.com/9cd7YE
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!