CODE FESTIVAL 2016 qual C Friction(800)

問題

考察

操作によって生じるコストを、生じる場所によって別々に考えてみることにします。そうすると、操作によってかかるコストの総和の下界が $\sum{(i列目とi+1列目で生じるコストの総和の最小値)}$ であることが分かります¹。これが達成可能かどうかを考えてみます。

列 $i$ に対する操作を整数 $i$ で表すことにします。まず、各 $i(1 \le i \le N-1)$ に対し、列 $i$ と列 $i+1$ の間で生じるコストの総和が最小となるような操作列を取ってきます。これらをもとに、全体に対する操作列を作ることを考えます。列 $i$ と列 $i+1$ の間でかかるコストは、列 $i$ と列 $i+1$ をどのような順番で操作したかだけによります。よって、全体に対する操作列の中で、 $i$ と $i+1$ が取ってきた操作列と同じ順番で並んでいればよいです。このような操作列は、まず $1$ と $2$ を並べてから、 $i=3,4,...,W$ を順番に適切な位置に(取ってきた操作列と同じ順番で現れるように)挿入すれば作ることができます。

これで下界が達成できることが分かりました。この下界を求めるためには $W=2$ の場合を解けばよく、DPを頑張るとできます。

#include<bits/stdc++.h>
using namespace std;
 
const int INF=1e9;
 
int main()
{
   int H,W; cin>>H>>W;
   vector<string> s(H);
   for(int i=0;i<H;i++) cin>>s[i];
 
   int ans=0;
   for(int j=0;j<W-1;j++){
      // cost[x][y]:=j列目がx個、j+1列目がy個の状態のときに操作にかかるコスト
      vector<vector<int>> cost(H+1,vector<int>(H+1));
      for(int x=0;x<=H;x++) for(int y=0;y<=H;y++){
         if(x==0 or y==0) cost[x][y]=0;
         else cost[x][y]=cost[x-1][y-1]+(s[x-1][j]==s[y-1][j+1]);
      }
      // dp[x][y]:=j列目がx個、j+1列目がy個の状態にするのにかかるコストの総和のmin
      vector<vector<int>> dp(H+1,vector<int>(H+1,INF));
      dp[H][H]=0;
      for(int x=H;x>=0;x--) for(int y=H;y>=0;y--){
         if(x+1<=H) dp[x][y]=min(dp[x][y],dp[x+1][y]+cost[x+1][y]);
         if(y+1<=H) dp[x][y]=min(dp[x][y],dp[x][y+1]+cost[x][y+1]);
      }
      ans+=dp[0][0];
   }
   cout<<ans<<endl;
   return 0;
}