现在的位置: 首页 > 算法 > 正文

poj1159

2016年10月22日 算法 ⁄ 共 396字 ⁄ 字号 评论关闭
#include
#include
#include
using namespace std;
int main(){
int n;
 
while(cin>>n&&n>=3&&n<=5000){
  char c[5001],d[5001];
  int dp[2][5001];
  getchar();
for(int i=1;i<=n;i++)
{
cin>>c[i];
d[n-i+1]=c[i];
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
  {
 
dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]);
  if(c[i]==d[j])
 
 dp[i%2][j]=max(dp[i%2][j],1+dp[(i-1)%2][j-1]);
  }
  cout<<n-dp[n%2][n]<<endl;
  }
  return 0;
}

抱歉!评论已关闭.