Codeforces 132 E. Bits of merry old England

問題

レジスタがm個あるコンピュータを考える。
n個の出力をさせたい。
出力するためには、あらかじめレジスタにその値を代入しなければならないが、
レジスタに値xを代入するにはxの2進数で立っているビットの数に等しいコストがかかる。
（出力にはコストはかからない）

与えられたn個の値を出力するのに必要なコストの最小値および、
そのときにコンピュータに与える命令列を出力せよ。

制約条件

n≦250
m≦26

方針

UTPC2011の問題Hhttp://www.utpc.jp/2011/slides/cache.pdfの方針と同じ。

値が生存する区間を考えて、そこに重みづけをして、グラフを作り費用流を流す。
同じ値が連続する場合があるので、それはグラフ上で負閉路になるので、あらかじめ取り除いておく。

本問では、命令列を具体的に出力してやる必要がある。
値の出力とかは詳しくはソースコード参照。生きている変数をmapで覚えておく。
フローが流れているところは変数を殺さないようにする。
フローが合流したら変数を殺す。

ちゃんと解説かく気力がつきた。

ソースコード

int n,m,a[300],b[300],mul[300];

void run(){
  cin>>n>>m;
  map<int,int> prev;
  int ans=0;
  V=0;
  rep(i,n){
    cin>>a[i];
    if(i==0||a[i-1]!=a[i])b[V++]=a[i];
    else mul[V-1]++;
  }
  
  rep(i,V){
    #define C(x) __builtin_popcount(x)
    if(prev.count(b[i])){
      add_edge(prev[b[i]]+1,i,1,-C(b[i]));
    }
    if(i)add_edge(i-1,i,INF,0);
    prev[b[i]]=i;
    ans+=C(b[i]);
  }
  ans+=min_cost_flow(0,V-1,m-1);
  
  bool use[26]={};
  map<int,int> var;
  vector<string> res;
  rep(i,V){
    stringstream ss;
    if(!var[b[i]]){
      int v=0;
      for(;use[v];v++);
      var[b[i]]=v+1;
      use[v]=1;
      stringstream tt;
      tt<<(char)(v+'a')<<"="<<b[i];
      res.pb(tt.str());
    }
    ss<<"print("<<(char)('a'+var[b[i]]-1)<<")";
    res.pb(ss.str());
    rep(j,mul[i])res.pb(res.back());

    bool erase=1;
    if(i<V-1){
      rep(j,G[i+1].size()){
        edge &e=G[i+1][j];
        if(e.to>i+1&&e.cap==0)erase=0;
      }
    }
    if(erase){
      use[var[b[i]]-1]=0;
      var[b[i]]=0;
    }
  }
  cout<<res.size()<<" "<<ans<<endl;
  rep(i,res.size())cout<<res[i]<<endl;
}