已知一個字符串a(chǎn)，b。 字符串b中包含數(shù)量不等的特殊符號“.”,“*”（字符串存在沒有特殊符號或者全由特殊符號組成的情 況）。 “.”表示該字符可以變成任意字符，“* ”表示該字符的前一個字符可以變成任意多個。 現(xiàn)在我們想知道b可否通過特 殊符號變成a。 a* 可以轉(zhuǎn)化為a,aa,aaa,aaaa…

這道題對于會做的同學(xué)很簡單，可以說能做出來的肯定做過這道題，因為如果連這么經(jīng)典的題都沒做過，那么一般做不出來這道題，對于第一次遇見這道題的同學(xué)來說，難度還是不小的。之前寫的這道題的題解AcWing 30 正則表達式匹配。

這道題與正則表達式匹配還是有點區(qū)別的，因為正則表達式匹配中*可以使得前面字符出現(xiàn)0次，處理起來更加復(fù)雜，而本題指出了*前面字符至少出現(xiàn)一次，這樣處理起來就簡單了。

狀態(tài)表示： f [ i ] [ j ] f[i][j] f[i][j]表示 a a a的前 i i i個字符與 b b b的前 j j j個字符是否匹配， t r u e true true表示匹配， f a l s e false false表示不匹配。

狀態(tài)邊界： f [ 0 ] [ 0 ] = t r u e f[0][0]=true f[0][0]=true表示兩個字符串都是空的情況是匹配的。

狀態(tài)轉(zhuǎn)移方程：

• b [ j ? 1 ] ? ! = ? ′ ? ′ b[j-1] \ !=\ '*' b[j?1]?!=?′?′時，
  f [ i ] [ j ] = { f [ i ? 1 ] [ j ? 1 ] if? a [ i ? 1 ] = = b [ j ? 1 ] ? o r ? b [ j ? 1 ] = = ′ . ′ f a l s e , a [ i ? 1 ] ! = b [ j ? 1 ] ? a n d ? b [ j ? 1 ] ! = ′ . ′ f[i][j]= \begin{cases} f[i-1][j-1]& \text{if\ $a[i-1]==b[j-1]\ or\ b[j-1]=='.'$}\\ \\ false,& \text{$a[i-1]!=b[j-1]\ and\ b[j-1]!='.'$} \end{cases} f[i][j]=??????f[i?1][j?1]false,?if?a[i?1]==b[j?1]?or?b[j?1]==′.′a[i?1]!=b[j?1]?and?b[j?1]!=′.′?

• b [ j ? 1 ] ? = = ? ′ ? ′ b[j-1] \ ==\ '*' b[j?1]?==?′?′時，

f [ i ] [ j ] = { f a l s e , if? b [ j ? 2 ] ? ! = ? a [ i ? 1 ] ?and? b [ j ? 2 ] ? ! = ? ′ . ′ f [ i ? 1 ] [ j ] ? ∣ ? f [ i ] [ j ? 1 ] , if? b [ j ? 2 ] ? = = ? a [ [ i ? 1 ] ?or? b [ j ? 2 ] ? = = ? ′ . ′ f[i][j]= \begin{cases} false, & \text{if\ $b[j-2]\ !=\ a[i-1]$\ and\ $b[j-2]\ !=\ '.'$}\\ \\ f[i-1][j]\ |\ f[i][j-1],& \text{if\ $b[j-2]\ ==\ a[[i-1]$\ or\ $b[j-2]\ ==\ '.'$} \end{cases} f[i][j]=??????false,f[i?1][j]?∣?f[i][j?1],?if?b[j?2]?!=?a[i?1]?and?b[j?2]?!=?′.′if?b[j?2]?==?a[[i?1]?or?b[j?2]?==?′.′?

由于狀態(tài)的初始值是false，所以我們只需要考慮狀態(tài)可能轉(zhuǎn)移為true的情況。即：
f [ i ] [ j ] = { f [ i ? 1 ] [ j ? 1 ] if? a [ i ? 1 ] = = b [ j ? 1 ] ? o r ? b [ j ? 1 ] = ′ . ′ f [ i ? 1 ] [ j ] ? ∣ ? f [ i ] [ j ? 1 ] , if? b [ j ? 1 ] ? = ? ′ ? ′ ?and?( b [ j ? 2 ] ? = = ? a [ [ i ? 1 ] ?or? b [ j ? 2 ] ? = = ? ′ . ′ ) f[i][j]= \begin{cases} f[i-1][j-1]& \text{if\ $a[i-1]==b[j-1]\ or\ b[j-1]='.'$}\\ \\ f[i-1][j]\ |\ f[i][j-1],& \text{if\ $b[j-1]\ =\ '*'$\ and\ ($b[j-2]\ ==\ a[[i-1]$\ or\ $b[j-2]\ ==\ '.'$)} \end{cases} f[i][j]=??????f[i?1][j?1]f[i?1][j]?∣?f[i][j?1],?if?a[i?1]==b[j?1]?or?b[j?1]=′.′if?b[j?1]?=?′?′?and?(b[j?2]?==?a[[i?1]?or?b[j?2]?==?′.′)?

以 a = ′ a a a a ′ , b = ′ a ? ′ a='aaaa',b='a*' a=′aaaa′,b=′a?′為例，在求狀態(tài) f [ 4 ] [ 2 ] f[4][2] f[4][2]時，先考慮*前面字符出現(xiàn)一次的情況，即 f [ i ] [ j ? 1 ] f[i][j-1] f[i][j?1]狀態(tài)；再考慮*前面字符出現(xiàn) n n n次的情況，此時如果匹配說明 f [ i ? 1 ] [ j ] f[i-1][j] f[i?1][j]也是匹配的，且匹配時*前面字符出現(xiàn)了 n ? 1 n-1 n?1次，再加上 a [ i ? 1 ] = = b [ j ? 2 ] ? o r ? b [ j ? 2 ] = ′ . ′ a[i-1]==b[j-2]\ or\ b[j-2]='.' a[i?1]==b[j?2]?or?b[j?2]=′.′的條件，足以使得 f [ i ] [ j ] f[i][j] f[i][j]匹配。

#include#include#includeusing namespace std;
const int N = 1005;
bool f[N][N];
std::string solution(std::string a, std::string b) {int n = a.size();
	int m = b.size();
	memset(f,false,sizeof f);
	f[0][0] = true;
	for(int i = 1; i<= n; i++) {for(int j = 1; j<= m; j++) {	if(a[i-1]==b[j-1] || b[j-1]=='.') f[i][j] = f[i-1][j-1];
			else if(b[j-1]=='*') {		if(b[j-2] == '.' || b[j-2] == a[i-1]) f[i][j] = f[i][j-1] | f[i-1][j];
			} else f[i][j] = false;
		}
	}
	if (f[n][m]) return "yes";
	else return "no";
}
int main() {std::string a;
	std::string b;
	getline(std::cin, a);;
	getline(std::cin, b);;
	std::string result = solution(a, b);
	std::cout<

#include#include#include#include#include#includeusing namespace std;
int fa[1005];
int find(int x) {if(x!=fa[x]) fa[x] = find(fa[x]);
	return fa[x];
}
int main() {int n;
	int m;
	std::cin>>n;
	std::cin>>m;
	int a,b;
	for(int i = 1; i<= 1000; i++) fa[i] = i;
	for(int i = 0; i< m; i++) {cin>>a>>b;
		if(fa[a] !=fa[b]) {	fa[find(a)] = find(b);
		}
	}
	sets;
	for(int i = 1; i<= 1000; i++) {fa[i] = find(i);
		s.insert(fa[i]);
	}
	int res = s.size() - 1 - (1000 - n);
	cout<

#include#include#include#include 
#includeusing namespace std;
int solution(int n, int m, std::vector& vec) {int res = 0;
	int t = 1e9;
	for(auto x : vec) {if (t<= m) {	int p = m / t * (x - t);
			res = max(res,p);
		}
		t = min(t,x);	
	}
	return res + m;
}
int main() {int n;
	int m;
	std::vectorvec;
	std::cin>>n;
	std::cin>>m;
	std::string line_0, token_0;
	getline(std::cin >>std::ws,line_0);
	std::stringstream tokens_0(line_0);
	while(std::getline(tokens_0, token_0, ' ')) {vec.push_back(std::stoi(token_0));
	}
	int result = solution(n, m,vec);
	std::cout<