* 풀이

t라는 시간이 가능하다면, 당연히 t+1시간에도 모든 상자를 옮기는 게 가능하기 때문에
이분검색으로 답을 정하여, 풀 수 있습니다.
답을 정하고나면, 그 답이 가능한지 검사하는 건 쉽습니다.
답을 t로 정했다면, 가장 무거운 상자 t개는 가장 무거운 크레인이 옮기고,
그 다음으로 무거운 상자 t개는 두번째로 무거운 크레인이 옮기고, 그 다음 t개는 세번째...
이런 식으로 하시면 됩니다.
답은 최소 (t*크레인 수 >= 상자 수) 조건이 만족하는 t값부터 가능합니다.

typedef vector<int> VI; #define PB push_back #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 ShipLoading { public:     int minimumTime(vector <int>, vector <string>); }; int ShipLoading::minimumTime(vector <int> cr, vector <string> boxes) {     string b;     FORE(it,boxes) b+=*it;     VI dt;     istringstream in(b);     int a;     while (in>>a) dt.PB(a);     sort(ALL(cr));     sort(ALL(dt));     reverse(ALL(cr));     reverse(ALL(dt));         int l=1,r=2500,m,dp=-1;     while (l*SZ(cr)<SZ(dt)) l++;     while (l<=r) {         m=(l+r)/2;         int no=0;         REP(i,SZ(dt)) {             int k=i/m;             if (dt[i]>cr[k]) { no=1; break; }         }         if (no) l=m+1;         else {             dp=m;             r=m-1;         }     }     return dp; }

 * 해법

기본적인 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)]; }

 * 풀이

문제만 보면 완벽하게 0-1 냅색 문제입니다. 그런데 문제는 제한 조건이 너무 크다는 데에 있습니다.
보통 0-1 냅색 문제는

 dy[i][j] = i번째 우표까지 j원을 썼을 때, 얻을 수 있는 최대 가치.

이렇게 정의되는데요. 이 문제에서 우표의 개수는 최대 32이지만, 각 우표의 가격이 최대 3천만이나 됩니다.
그렇다면 저런 식으로 풀자면 dy[32][30000000*32]의 메모리를 잡아야 하는데, 당연히 불가능하겠죠.

그렇다면 개수가 32개밖에 안 되니까 2^32의 경우를 모두 보는 고려해보는 건 어떨까요?
이것도 역시 안됩니다. 2^32는 너무 크죠. 42억 가지를 고려하기엔 컴퓨터가 너무 느립니다.

그래서 제가 쓴 방법은 이 2가지를 적절히 섞은 방법입니다.

우선 n개의 우표를 반으로 나눠서 A그룹, B그룹으로 나눕니다.
그래서 각각 2^(n/2)의 경우를 모두 고려해서 배열(da, db)에 (가격(cost), 가치(value))를 저장합니다.

그리고 각각 그룹을 가치 순으로 정렬합니다.
그리고나서 가치가 높은 것부터 보면서 DP를 적용합니다.

da[i].cost = da[i].value 이상의 가치를 만들 때 필요한 최소한의 가격.
da[i].cost = min(da[i].cost, da[i+1].cost) // 더 높은 가치를 만드는데 더 낮은 가격이 가능하다면...

DP를 적용한 후에는 간단합니다. A그룹에서 가능한 모든 경우를 보면서
K가치를 만드는데 필요한 최소한의 cost를 B그룹에서 찾아주며 답을 갱신하면 됩니다.
가치 순으로 정렬이 되어 있으니 이분검색으로 찾는 게 가능하겠죠.
그래서 O( 2^(n/2) * log(2^(n/2)) ) 다시 쓰자면 O( 2^(n/2) * n ) 정도가 되겠네요.

아 그리고, 처음에 가지고 있던 우표는 전부 돈으로 바꿨다고 치면, 마지막에 구한 답에서
그 돈을 빼주면 되겠죠? (그래서 음수가 된다면 이미 K가치 이상 가졌다는 뜻이죠.)

typedef long long LL; typedef long double LD; typedef vector<int> VI; typedef pair<int,int> PII; typedef vector<PII> VPII; #define MP make_pair #define ST first #define ND second #define PB push_back #define FOR(i,a,b) for( int i=(a); i<(b); ++i) #define FORD(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) struct ele {     int v,c;         bool operator <(ele t) const     {         if (v==t.v) return c>t.c; // 가치가 같을 때는 가격이 큰 게 앞에 오도록..         return v<t.v;     } }; class CollectingPostmarks { public:     int amountOfMoney(vector <int>, vector <int>, vector <int>, int); }; int CollectingPostmarks::amountOfMoney(vector <int> pr, vector <int> ha, vector <int> va, int K) {     int ini=0;     REP(i,SZ(ha))         ini+=pr[ha[i]]; // 처음 가지고 있던 우표는 모두 돈으로 바꾼다.         int n=SZ(pr);     vector<ele> da,db;         REP(i,1<<(n/2)) { // A그룹 저장         ele tmp;         tmp.c=tmp.v=0;         REP(j,n/2)             if (i&(1<<j)) {                 tmp.c+=pr[j];                 tmp.v+=va[j];             }         da.PB(tmp);     }     REP(i,1<<(n-n/2)) { // B그룹 저장         ele tmp;         tmp.c=tmp.v=0;         REP(j,n-n/2)             if (i&(1<<j)) {                 tmp.c+=pr[n/2+j];                 tmp.v+=va[n/2+j];             }         db.PB(tmp);     }         sort(ALL(da)); // 가치 순으로 정렬     sort(ALL(db));         FORD(i,SZ(da)-2,-1) da[i].c=min(da[i].c,da[i+1].c); // DP!     FORD(i,SZ(db)-2,-1) db[i].c=min(db[i].c,db[i+1].c);            int dp=2023423423;     REP(i,SZ(da)) { // A그룹에서 모든 경우를 보며         int rem=K-da[i].v; // B그룹에서 필요한 가치 rem을 구한다.         if (rem<=0) dp=min(dp,da[i].c);         else {             if (db[SZ(db)-1].v<rem) continue;             ele tmp;             tmp.c=2023423423;             tmp.v=rem;             tmp=*lower_bound(ALL(db),tmp); // 이분검색             dp=min(dp,da[i].c+tmp.c);         }     }     if (dp==2023423423) return -1;     dp-=ini; // 처음 가지고 있던 돈을 뺀다.     dp=max(dp,0);     return dp; }

 * 해법

저는 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; }