SRM 597 DIV1 Easy - LittleElephantAndString (○)

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12854&rd=15709

文字列の長さが同じである、文字列Aと文字列Bが与えられる。
文字列Aの任意の文字を1つ選んで、先頭に持ってくる動作を繰り返して文字列Bにしたい。
このとき、必要な最小の操作回数を求める。
どうしても文字列Bにできないときは-1を返す。

解き方


・文字列Aの先頭からx文字と、文字列Bの後ろからx文字のうち最長のxを求め、
 残りの文字列長が答えになる?
・サンプルをみると、Aの部分文字列のうち間の文字をとることで部分文字列Bにもできるので
 そうではなさそう。

・間の文字を取れるということは、Aの部分文字列とBの最後からx文字の文字列のうち
 最長のxをとれればよさそう。
・最長部分文字列の問題なのでdpでxを求める。

→System Passed

・AもBも部分文字列であればdpだが、Bは固定文字列なので貪欲法でもよかった。

コード


using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class LittleElephantAndString {

public: int getNumber(string A, string B) {
int n=A.size();


int a[26]={},b[26]={};
FORE(i,0,n)a[A[i]-'A']++;
FORE(i,0,n)b[B[i]-'A']++;
FORE(i,0,26)if(a[i]!=b[i])return -1;

int dp[60][60];

for(int len=n;len>0;len--){
memset(dp,0,sizeof(dp));
dp[0][n-len]=1;
FORE(i,0,n)FORE(j,0,n)if(dp[i][j]){
if(A[i]==B[j])dp[i+1][j+1]=1;
dp[i+1][j]=1;
}
FORE(i,0,n+1)if(dp[i][n])return n-len;
}

return n;
}

};
このエントリーをはてなブックマークに追加