* 해법

기본적인 DP 문제입니다.

dy[i] = sentence의 index i-1까지 만들 때, 최소의 cost
substr(i,j) = sentence의 index i부터 알파벳 개수 j개를 가지는 substring
words[] = 단어들

dy[i] = min(dy[i-len] + cost(substr(i-len,len), words[j])) // len = length of words[j]

이런 식으로 하시면 됩니다.

cost함수는 입력으로 들어온 두 단어가 서로 재배치해서 같아질 수 있는지 검사해서
불가능하다면 무한대를 리턴하고, 가능하다면 그 cost를 계산하면 되는데요.
재배치해서 같아질 수 있는지는 각각을 정렬하고 같은지 비교해보면 됩니다.

아래는 제가 실제 대회 때 작성했던 코드인데.. 점화식을 조금 달리 이용했습니다.
i대신 i+len로 했네요.

#define REP(i,n) for(int i=0; i<(n); ++i) #define ALL(X) (X).begin(),(X).end() #define SZ(X) (int)(X).size()   class SentenceDecomposition { public:   int decompose(string, vector <string>); };   int anag(string a,string b) {   sort(ALL(a));   sort(ALL(b));   return a==b; }   int cost(string a,string b) {   int c=0;   REP(i,min(SZ(b),SZ(a)))     if (a[i]!=b[i]) c++;   return c; }   int dy[2500];   int SentenceDecomposition::decompose(string sent, vector <string> val) {   memset(dy,63,sizeof(dy));   dy[0]=0;     REP(i,SZ(sent))   REP(j,SZ(val)) {     int len=SZ(val[j]);     if (anag(sent.substr(i,len),val[j])) {       int cst=cost(sent.substr(i,len),val[j]);       dy[i+len]=min(dy[i+len],dy[i]+cst);     }   }   if (dy[SZ(sent)]>100) return -1;   return dy[SZ(sent)]; }

 * 문제 풀이

 length가 매우 크기(10억) 때문에 아쉽게도 iteration으로는 해결할 수가 없습니다. 하지만 Matrix Multiplication(행렬 곱셈)을 사용하면 보다 쉽게 접근할 수가 있지요.

 우선 입력으로 받은 numbers에서 Lucky Number들을 골라냅니다. 그리고 중복되는 Lucky Number들을 지워줍니다.

 위 와 같이 처리를 했다면, 어떤 Lucky Number가 있더라도 앞자리와 끝자리만 고려해도 됩니다. 474나 4774나 4474 모두 4로 시작해서 4로 끝나는 수의 의미만 가질 뿐이고, 다른 의미는 없거든요. 그러면 아래와 같은 2 by 2 Matrix를 생성합니다.

            [ 4로 시작해서 4로 끝나는 수,  4로 시작해서 7로 끝나는 수]
  A =    [ 7로 시작해서 4로 끝나는 수,  7로 시작해서 7로 끝나는 수]

 우 리가 구하려는 답은 A ^ (length) 를 구하여 2 by 2 matrix를 이루고 있는 각 수의 합이 됩니다. (뒤에 간단한 증명을 적어두겠습니다.) 그러면 행렬의 length 제곱을 해야 하는데 이 부분은 log(length)번으로 해결할 수 있지요. length가 짝수라면 (length / 2)의 제곱을, 홀수라면 (length / 2) ^2 * (this)를 해주면 되기 때문입니다. 큰 수의 나머지와 관련된 문제는  (B + C) % p = ((B % p) + (C % p)) % p 를 알고 있다면 쉽게 풀 수 있습니다.

Proof:
 T[i][j][k]를 (전체 i개의 Lucky Number를 사용해서, A[0]의 첫 자리가 j이고 A[i - 1]의 마지막 자리가 k인 Sequence의 수) 라고 정의합시다.

 위에서의 행렬은 T[1][4][4]. T[1][4][7]. T[1][7][4]. T[1][7][7]을 의미한다고 보면 되지요.

 여 기서 T[k][4][4]를 구한다고 가정하면, T[k][4][4] = T[k - 1][4][7] * T[1][7][4] + T[k - 1][4][4] * T[1][4][4] 라고 볼 수 있습니다. (정의를 천천히 되새겨 봅시다.)

 위와 같은 방식으로 모든 table을 채울 수가 있지요. :)

 * 해법

저는 cakeLength가 그리 크지 않길래 정수 좌표를 모두 격자로 나누고,
BFS로 채우는 방법을 택했습니다.
수직선 수평선에 붙어있는 격자점에서는 선을 넘어가지 못하게 해야 하죠.
제 코드에서는 go배열이 그 역할을 합니다.

#define MP make_pair #define X first #define Y second #define PB push_back #define FOR(i,a,b) for( int i=(a); i<(b); ++i) #define REP(i,n) for(int i=0; i<(n); ++i) #define ALL(X) (X).begin(),(X).end() #define SZ(X) (int)(X).size() #define FORE(it,X) for(__typeof((X).begin()) it=(X).begin(); it!=(X).end(); ++it)   class HoleCakeCuts { public:   int cutTheCake(int, int, vector <int>, vector <int>); };   int hy[4]={0,0,-1,1}; int hx[4]={-1,1,0,0}; int chk[205][205]; int go[205][205]; int cakl;   void bfs(int x,int y) {   queue<PII> q;     chk[x][y]=1;   q.push(MP(x,y));   while (!q.empty()) {     PII ka=q.front(); q.pop();     x=ka.X,y=ka.Y;         REP(i,4) {       int py,px;       px=x+hx[i];       py=y+hy[i];       if (go[x][y]&(1<<i)) continue;       if (px<0 || px>=cakl*2) continue;       if (py<0 || py>=cakl*2) continue;       if (chk[px][py]) continue;       chk[px][py]=1;       q.push(MP(px,py));     }   } }   int HoleCakeCuts::cutTheCake(int ca, int hole, vector <int> ycut, vector <int> xcut) {   cakl=ca;   memset(chk,0,sizeof(chk));   memset(go,0,sizeof(go));   FOR(i,-hole+cakl,hole+cakl)   FOR(j,-hole+cakl,hole+cakl)     chk[i][j]=1;   REP(i,SZ(ycut)) {     int y=ycut[i]+cakl;     REP(j,cakl*2+1) {       go[j][y-1]^=8;       go[j][y]^=4;     }   }   REP(i,SZ(xcut)) {     int x=xcut[i]+cakl;     REP(j,cakl*2+1) {       go[x-1][j]^=2;       go[x][j]^=1;     }   }     int dp=0;   REP(i,cakl*2)   REP(j,cakl*2)     if (chk[i][j]==0) {       dp++;       bfs(i,j);     }   return dp; }

그런데 다른 해법도 존재했습니다. 저랑 같은 방에서 하던 _Romka_라는 분의 해법인데요.
저는 처음에 DFS나 BFS가 정해라고 생각하고, "뭐야, 이거 당연히 안 되겠지~"
이러면서 첼린지를 했는데, 바로 실패해서, 더이상 첼린지는 안 하고 sys test만 기다렸습니다.
근데 sys test 끝나고보니, 이 코드가 통과하더군요.
어떤 방법인지는 각자의 숙제로 남길게요 >_<

int HoleCakeCuts::cutTheCake(int cl, int hl, vector <int> h, vector <int> v) {     sort( h.begin(), h.end() );     sort( v.begin(), v.end() );     ans = (h.size()+1)*(v.size()+1);     int ch = 0;     int cv = 0;     for ( int i=0; i<h.size(); i++ )      if ( h[i] >= -hl && h[i] <= hl ) ch++;     for ( int i=0; i<v.size(); i++ )      if ( v[i] >= -hl && v[i] <= hl ) cv++;          if ( ch > 0 || cv > 0 )      ans -= ( cv-1 )*( ch-1 );   return ans; }