蓝桥杯2016年第七届真题-密码脱落

解题思路:就是公共最长序列的模板套用

注意事项:

参考代码:

#include <bits/stdc++.h>

using namespace std;

int maxlen[1000][1000];

int main()

{

    string sz1;

cin>>sz1;

string sz2=sz1;

reverse(sz1.begin(),sz1.end());

int length1=sz1.length();

int length2=sz2.length();

int nTemp;

int i,j;

for(i=0;i<=length1;i++)

{

maxlen[i][0]=0;

} 

for(j=0;j<=length2;j++)

{

maxlen[0][j]=0;

}

for(i=1;i<=length1;i++)

{

for(j=1;j<=length2;j++)

{

if(sz1[i-1]==sz2[j-1])

maxlen[i][j]=maxlen[i-1][j-1]+1;

else

maxlen[i][j]=max(maxlen[i][j-1],maxlen[i-1][j]);

}

}

cout<<sz1.length()-maxlen[length1][length2]<<endl;

return 0;

}