SRM 411 DIV1 Easy - SentenceDecomposition (復習○)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=8692&rd=12183

・ある文と、単語の一覧が与えられる。
・ある文を、与えられた単語を使って変換したい。
・与えられた単語の順番を変えることで、ある文の一部と一致すればその一部を変換することができる。
・変換するコストは、順番を変えた数になる。

このとき、変換するコストの最小値を求める。変換できなければー1を返す。

解き方


dpを使って解く。
dp[n=与えられた文字数]をとり、dp[i]をi番目までの最小のコストと定義する。
dp[i]はiまでの文字をまとめて変換できるか、
j<iとなるdp[j]が存在する場合j+1~iまでの文字が変換できるかを判定し
最小値を更新していく。

コード


class SentenceDecomposition {

public:

int rec(string s1,string s2){
int cost=0;
FORE(i,0,s1.size())if(s1[i]!=s2[i])cost++;
sort(all(s1));
sort(all(s2));
return s1==s2 ? cost : 1e+9;
}

int decompose(string sentence, vector<string> validWords) {
int n=sentence.size();
int dp[n+1];

FORE(i,0,n+1)dp[i]=1e+9;
dp[0]=0;

for(int i=0;i<n;i++)if(dp[i]!=1e+9){
FORE(j,0,validWords.size()){
int len=validWords[j].size();
if(i+len-1<n){
int cost=rec(sentence.substr(i,len),validWords[j]);
dp[i+len]=min(dp[i+len],dp[i]+cost);
}
}
}

return dp[n]>=1e+9 ? -1 : dp[n];
}

};

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 SentenceDecomposition {

public:

int calc(string s1,string s2){
if(s1.size()!=s2.size())return 1e+9;
string str1=s1,str2=s2;
sort(all(s1));
sort(all(s2));
if(s1!=s2)return 1e+9;

int ret=0;
FORE(i,0,s1.size())ret+=(str1[i]!=str2[i]);
return ret;
}


int decompose(string str, vector<string> words) {
int n=str.size();
int d[n][n];
FORE(i,0,n)FORE(j,0,n)d[i][j]=1e+9;
FORE(i,0,n)FORE(j,i,n)FORE(k,0,words.size()){
d[i][j]=min(d[i][j],calc(words[k],str.substr(i,j-i+1)));
}

int dp[n+1];
FORE(i,0,n+1)dp[i]=1e+9;
dp[0]=0;
FORE(i,0,n)FORE(j,0,i+1){
dp[i+1]=min(dp[i+1],dp[j]+d[j][i]);
}

return dp[n]==1e+9 ? -1 : dp[n];
}

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