hdu6170
题目大意 :
类似正则匹配
这个题开始的时候没有写出来，想到了状态的设法，如果设dp[i][j]代表第一个串的前i项能否匹配第二个串的前j项，状态个数很明显是n2的，然而一直苦于*符号的匹配，找不到好的转移方程，不管怎么想都是n3的转移复杂度，当s2[j]是*的时候，dp[i][j] <-dp[pre][j] 其中pre可以取的值的要求是：对于所有的pre<=k<=i s1【k】=s1【i】
这个转移不是不可以优化，这显然是一个连续的区间，可以采取rmq预处理来实现降低时间复杂度到n2lgn，但是这样写似乎显得小题大做，并且时间复杂度不是很理想，可能卡在时间的边界上然后time limited。
最后看了题解，发现可以O(1)转移，但是网上的题解的证明过程显得苍白无力，甚至有不少代码是错的，ac不过是因为数据弱而已。
我想了很久，最终得到了*的转移： 考虑s1[i]和s1[i-1]是否相等，如果不相等的话，那么*要么贡献0次由dp[i][j-2]转移，要么贡献1次由dp[i][j-1]转移，复杂的是相等的情况，*贡献0次和1次是一样的，因为s1[i]和s1[i-1]相等，所以*可能贡献多次(多指的是大于等于二)。
分析贡献多次的时候:从dp[i][j]=1必要条件入手，因为多次，所以如果他少贡献一次的话，dp[i-1][j]也为1，且有条件s1[i-1]=s2[j-1]或s2[j-1]=='.'。
然后证明此必要条件的充分性，由于dp[i-1][j]=1且s1[i-1]和s2[j-1]是一样的，那么*多贡献一次就可以了。因为s1[i-1]和s2[j-1]是一样的，所以可以多贡献一次。
于是（dp[i-1][j]=1且s1[i-1]和s2[j-1]一样）与（贡献多次的dp[i][j]=1）等价。
这前的每一个细节都很重要，为什么要求s1[i-1]和s2[j-1]是一样的，如果不做此要求，就过不了这个例子：
aa
ab*
至于dp边界的处理，特别简单，我们改变输入数据s1 和s2为（“@@”+s1）和(“@@”+s2)，边界就特别特别简单了。
虽说简单，但我还是搞错了，忽略了一种情况因为少了下面的代码，
然后就过不了这个反例
c
a*b*c
因为什么呢?因为”@@”居然可以和”@@a*”匹配,简直是恐怖。
#include<bits/stdc++.h> using namespace std; int main(){ int T; scanf("%d ",&T); while(T--){ static const int maxn=2600; static char s1[maxn],s2[maxn]; static int dp[maxn][maxn]; //scanf("%s%s",s1+2,s2+2); gets(s1+2); gets(s2+2); s1[0]=s2[0]=s1[1]=s2[1]='@'; int l1=strlen(s1); int l2=strlen(s2); dp[0][0]=dp[1][1]=1; for(int j=2;j<l2;j++){ if(s2[j]=='*')dp[1][j]=dp[1][j-2]; else dp[1][j]=0; } for(int i=2;i<l1;i++){ for(int j=2;j<l2;j++){ if(s2[j]=='.')dp[i][j]=dp[i-1][j-1]; else if(s2[j]=='*'){ if(s1[i]!=s1[i-1]){//最多贡献一次 dp[i][j]=dp[i][j-2]||dp[i][j-1]; } else{ dp[i][j]=dp[i][j-2]||dp[i][j-1]||(dp[i-1][j]&&(s1[i-1]==s2[j-1]||s2[j-1]=='.')); } } else dp[i][j]=dp[i-1][j-1]&&s1[i]==s2[j]; } } cout<<(dp[l1-1][l2-1]?"yes":"no")<<endl; } } /* --------aa --------ab* */
- 本文作者： fightinggg
- 本文链接： http://fightinggg.github.io/yilia/yilia/hdu6170.html
- 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！