第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛--D-psd面试

#include<cstdio> 
#include<cstring> 
#include<algorithm> 
#include<iostream> 
#include<string> 
#include<vector> 
#include<stack> 
#include<bitset> 
#include<cstdlib> 
#include<cmath> 
#include<set> 
#include<list> 
#include<deque> 
#include<map> 
#include<queue>
#include<algorithm> 
using namespace std; 
typedef long long ll; 
const double PI = acos(-1.0); 
const double eps = 1e-6; 
const int INF = 1000000000; 
const int maxn = 100; 
char str1[2000],s2[2000];
int dp[2000][2000];
int main()
{  
    while(cin>>str1)
    {
        int l=strlen(str1),to=0;
        for(int i=0;str1[i];i++)
        {
            if(str1[i]>='a'&&str1[i]<='z')
            str1[i]=str1[i]-'a'+'A';
        }
        for(int i=l-1;i>=0;i--)
        {
            s2[to++]=str1[i];
        }
        s2[to]='\0';
         memset(dp, 0, sizeof(dp)); 
        for( int i = 0; i < l; i++)
            for(int  j = 0; j < to; j++)
                if(str1[i] == s2[j])
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                else
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
        cout<<l-dp[l][to]<<endl;

    }

    return 0;
}