Spoj, dynamic-programming: AIBOHP - Aibohphobia

August 12, 2016
spoj

给一个字符串，求最少插入多少个字符，可以使得这个字符串是回文的。

可以这样想：我们假设它已经是回文的，那么把这个字符串逆序，如果它是回文的，那么对应的每个字符应该相等。可以它不是回文的，那么就需要尽量少地加一些字符，加多少呢？那么需要知道当前的最长连续公共子序列的长度len，把不相等的那些字符串加进去就成为了回文的。加进去的字符的最少个数 = 字符串长度 - 原先的字符串和它的逆序字符串的最长连续公共子序列的长度。

问题就转化为求两个序列的最长公共子序列。这个就简单了。

因为懒并且想省时间，所以就用了一些宏，这让程序变得不易读，还好程序比较简单，不太影响吧。反正以后也不会再读。。了解思路就可以了。

/*
 * =====================================================================================
 *
 *       Filename:  main.cpp
 *
 *    Description:  http://www.spoj.com/problems/AIBOHP/
 *
 *        Version:  1.0
 *        Created:  08/12/2016 18:27:30
 *       Compiler:  g++
 *
 *         Author:  Sabastian (liuxueyang.github.io), liuxueyang457@gmail.com
 *
 * =====================================================================================
 */
#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define rep(i, a, n) for (int i = a; i < n; ++i)
#define per(i, a, n) for (int i = n-1; i > a; --i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef map<int,int> MI;
typedef long long ll;
typedef pair<int,int> PII;
const ll MOD=1000000007;
const int N=6120;
int a[N][N];
char s[N],t[N],str[N];
  int
main ( void )
{
#ifndef  ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
#endif     /* -----  ONLINE_JUDGE  ----- */

  int T;cin>>T;while(T--){
    memset(a,0,sizeof(a));
    cin>>str;int len=strlen(str);
    rep(i,0,len)s[i+1]=str[i];
    rep(i,1,len+1)t[len+1-i]=s[i];
    rep(i,1,len+1){
      rep(j,1,len+1){
        if(s[i]==t[j]){
          a[i][j]=max(a[i][j],a[i-1][j-1]+1);
        }
        else {
          int mm=max(a[i-1][j],a[i][j-1]);
          a[i][j]=max(a[i][j],mm);
        }
      }
    }
    cout<<len-a[len][len]<<endl;
  }

  return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

Read more