对答案 题解【DP】【字符串】
点击量:230
需要一点点复杂度优化+常数优化
题目背景
企鹅豆豆做完了作业,找你帮他检查。
题目描述
豆豆写的作业由小写字母组成。但由于一道题有多种答案,所以答案中除了小写字母以外还有
.
和*
。
.
字符可以变成任意一个小写字母。x*
可以变成(空串)、
x
、xx
、xxx
等等,即可以变任意个字符x
(其中x
可以是小写字符或者.
)现在,有标准答案以及豆豆的作业,请你判断豆豆的作业是不是完全正确的。
数据保证
*
不会出现在开头,不会有两个连续的*
。输入输出格式
输入格式:
第一行一个整数\(T\),表示数据组数。
对于每组数据,第一行一个字符串,表示豆豆的作业。第二行一个字符串,表示答案。
输出格式:
对于每组数据,输出一行一个字符串,如果作业正确输出
yes
,否则输出no
。输入输出样例
输入样例#1:3 aa a* abb a.* abb aab输出样例#1:yes yes no说明
对于\(30\%\)的数据,字符串长度\(\le 10\);
对于\(70\%\)的数据,字符串长度\(\le 200\);
对于\(100\%\)的数据,字符串长度\(\le 2500,T\le 15\);
题解:
一开始看这个题感觉是模拟,分别扫一遍两个字符串就可以了。但是发现有很多状态都需要决策,比如*
需要代表的字符个数以及是否代表一个字符,还会影响.*
中.
的决策。因此对于决策我们考虑\(\text{DP}\)。
设\(f[i][j]\)表示作业串匹配到第\(j\)位,答案串匹配到第\(i\)位是否合法。考虑\(O(n^2)\)枚举下标,然后进行转移,需要区分这一位后面有没有跟*
和这一位是不是.
。如果后面有*
则这一位先不管,否则判断\(s_j=t_i\)或\(t_i=’.’\),如果满足则\(f[i][j]=f[i-1][j-1]\),否则为\(0\)。
如果\(t\)这一位刚好是*
,说明\(t\)前面一位可以出现\(k(k\in \bf N)\)次。那么\(f[i][j]\)可以不出现,即直接转移\(f[i-2][j-1]\)的状态,当\(f[i][j]\)出现时,需要满足\(s_j=t_{i-1}\)才能转移。设\(s_j\)前面有\(len\)个和它一样的字符,则*
可以代表\([0,len+1]\)个这样的字符,从而转移来源是\(\max\limits_{j-len\le p<j}f[i-2][p]\)。同样地,\(s_{j-len-1}\)是\(s_j\)前面第一个和它不一样的字符,此时也可以从这里转移,所以\(f[i][j]\)还需要\(\text{or}f[i-2][j-len-1]\)。
可以看出,上述\(\max\)的计算是\(O(n)\)的,因此时间复杂度变成了\(O(n^3)\),此时期望得分\(70\);我们要想办法优化掉一个\(n\)。
考虑前缀和优化,则每个点存的前缀和是从他往前数第一个和它不同的元素开始到它之间的这些元素中,dp值的最大值。每次遇到\(s_{j-1}\ne s_j\)时,需要重新计算,这样一来时间复杂度变成了\(O(n^2)\)。
还有一种优化是转移优化,也就是如果\(s_j\)用了\(t_i\)位置的*
\(k\)次,那么当\(s_{j+1}=s_j\)时,\(s_{j+1}\)可以直接用第\(k+1\)次。因此上面那行可以被优化为
\(\tt if s[j]==s[j-1] then\)
\(f[i][j]=f[i-2][j-1]|f[i][j-1]\)。
关于常数优化
每次统计前缀和需要\(O(n)\),一共\(n\)次,导致增加一个常数,因此后面一种方法会稍微卡常。因为内存连续,所以数组中的最后一维应该尽可能是循环的最内层,可以稍微跑得快一点。
Code:
#include<cstdio>
#include<cstring>
char s[2505],t[2505];
bool f[2505][2505],sum[2505][2505];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",s+1);
scanf("%s",t+1);
int n=strlen(s+1);
int m=strlen(t+1);
f[0][0]=true;//这里f[i][j]与上面相反 分别表示s_i和t_j
sum[0][0]=true;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
if(t[j+1]!='*')//判断后面一位是不是*
{
if(t[j]!='*')//判断当前位是不是*
{
if(s[i]==t[j]||t[j]=='.')
f[i][j]=f[i-1][j-1];
else
f[i][j]=false;
}
else
{
f[i][j]=f[i][j-2];
if(s[i]==t[j-1]||t[j-1]=='.')
{
if(s[i]==s[i-1])
f[i][j]|=sum[i-1][j-2];
else
f[i][j]|=f[i-1][j-2];
/******或者******/
if(s[i]==s[i-1])
f[i][j]|=(f[i-1][j]|f[i-1][j-2]);
else
f[i][j]|=f[i-1][j-2];
}
}
}
if(s[i]!=s[i-1])
for(int j=0;j<=m;++j)
sum[i][j]=f[i-1][j]|f[i][j];
else
for(int j=0;j<=m;++j)
sum[i][j]=sum[i-1][j]|f[i][j];
}
if(f[n][m])
puts("yes");
else
puts("no");
}
return 0;
}
… [Trackback]
[…] Read More on that Topic: wjyyy.top/2716.html […]