読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

UVa 11753 : Creating Palindrome

UVa 再帰 文字列

問題リンク:http://uva.onlinejudge.org/external/117/11753.html

問題概要:
文字列に文字をいくつか追加して回文にしたい
K回以下の追加で回文にできるか?

解法:
実際に再帰で試してみて最小の追加回数を求める

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int N,K;
int v[10010];

int dfs(int L,int R,int k){
  if( k > K ) return K+1;
  if( L >= R ) return k;
  if( v[L] == v[R-1] ) return dfs(L+1,R-1,k);
  return min(dfs(L+1,R,k+1),dfs(L,R-1,k+1));
}

int main(){
  int T,CNT=1;
  cin >> T;
  while( T-- ){
    printf("Case %d: ",CNT++);
    cin >> N >> K;
    rep(i,N) cin >> v[i];
    int res = dfs(0,N,0);
    if( res == 0 )     puts("Too easy");
    else if( res > K ) puts("Too difficult");
    else               printf("%d\n",res);
  }
  return 0;
}