题目:HDOJ-5510
这道题是在一次团队练习赛中,在共同的努力下拿下的。
一开始,我们是穷举,毫无疑问的TE了。
后来,我联想到了在这道题中存在的传递性。即a在b中,b在c中,则一定有a在c中。
我当时觉得应该按照传递性的方向进行递推,事实证明,这样的递推方向会中断,无法一直递推下去,这使得我们当时陷入了困境。
但机智的队友却向相反的方向前进,由于这道题目是求最大的,可能他当时从这点出发想到从后向前递推,成功了。
不得不承认他的代码风格比我好(不愧是学软件工程的),模板能力比我强得多,很多时候我有想法却无法验证,由于部分算法没有掌握,拖慢了整个队伍的节奏。
另外:很好奇strstr()这个API他是怎么知道的,而且还不是第一次在关键时候使用这样我完全没有听说过的API。
虽说程序通过了,不过,我还是想说,在递推终止后对递推前的字符串进行检验时,可以使用二分,500这个数量级不大,二分没有明显效果,但毕竟是一个改良。
核心代码:
for(int i=k-1;i>=0;i--)
{
if(!strstr(s[i],s[i-1]))//判断s【i-1】是否是s【i】的子串
{
ans=max(ans,i);
for(int j=i+1;j<k;j++)//PS:可以使用二分
{
if(!strstr(s[j],s[i-1]))
{
ans=max(ans,j);
}
}
}
}