SRM551 Div.1

練習です。

250 ColorfulChocolates

文字列が与えられて、隣接する2つをmaxSwap回swapしたときの
連続する同じ文字の最大の長さを求める。

方針は2つ

• 同じ文字に注目して、中央にあるものに寄せるときのコストといくつくっつけられるかを計算
• 区間を決めて、ある文字をその区間に詰めるときのコストを計算

文字列の長さは高々50なので、後者の方が実装が楽そうなのでそっちを選ぶ。

コードは以下

     int maximumSpread(string c, int ms) {
         int n = c.size();
         int ret = 0;
         for(int i=0;i<n;i++){
             for(int j=i;j<n;j++){
                 for(int k=0;k<n;k++){
                     int numSwap = 0;
                     int adj = 0;
                     for(int l=k;l<n;l++){
                         if(c[k] == c[l] && adj < j - i + 1){
                             numSwap += abs(l - (i+adj));
                             adj++;
                         }
                     }
                     if(numSwap <= ms && j-i+1 == adj){
                         ret = max(ret, adj);
                     }
                 }
             }
         }
         return ret;
     }

500　ColorfulWolves

n色の色があって、i->jに変更できるかできないかのmatrixが与えられる。
色を変更する場合は最も小さい番号の色に変わるが、
ある色へ変更できる->変更できないと変化させることができる。
色0から色n-1になるまでに何回この変化をさせなければいけないか。

例えばある色iからの行が

NNYYNY

で、最後のYを使いたいと思ったらそれより前のY2つをNに変化させる必要がある。
なので、そのコストを持つmatrixを作ってWFすればいい。

コード

     int getmin(vector <string> cm) {
         int n = cm[0].size();
         int cost[n][n];

         fill((int *)cost, (int *)cost + n * n, INF);
         for(int i=0;i<n;i++){
             int cnt = 0;
             for(int j=0;j<n;j++){
                 if(cm[i][j] == 'Y'){
                         cost[i][j] = cnt;
                         cnt++;
                 }
             }
         }
         for(int r=0;r<n;r++){
             for(int p=0;p<n;p++){
                 for(int q=0;q<n;q++){
                     cost[p][q] = min(cost[p][q], cost[p][r] + cost[r][q]);
                 }
             }
         }

         return cost[0][n-1] == INF?-1:cost[0][n-1];
     }