275 P8XGraphBuilder

2011-12-20

19:06 |

総当りで TLE、その後 editorial 見てヒントをもらって書いた(practice system test pass)

辺の数が頂点数-1で連結なので木になる。

残りが remain 個あったとして、どれかの葉に i 個の子ノードを加える操作を（できるなら）したときの最大 score を返す。

（葉だけに加えてよいのは、葉でないノードに加える選択肢は以前のどこかで葉に加える操作に含まれるので）

その際、ルートノードだったら次数 i のノードが１個増え、次数１の子ノードが i 個増える。

ルートじゃないときは、次数１のノード（親への辺の分）が１個減り、次数 i+1 のノードが１個増え、次数１の子ノードが i 個増える。

で最初にルートが置いてあるとして、remain == 頂点数-1 として再帰関数をよびだす。

それをメモ化。

全然DP脳じゃないけどメモ化再帰脳には少しなってきたような気がするｗ

class P8XGraphBuilder {
   public:
   VI dp;
   int f(vector<int>& scores, int remain) {
       if(remain==0) return 0;
       if(dp[remain]!=-1) return dp[remain];
       int ans = -100;
       for(int i=1;i<=remain;i++) {
           //cout<<"remain "<<remain<<" take "<<i<<" "<<scores[i]<<" "<<endl;
           int a = f(scores, remain-i);
           //cout<<"remain "<<remain<<" take "<<i<<" "<<scores[i]<<" "<<a<<" -> "<<-scores[0]+scores[i]+i*scores[0]+a<<endl;
           ans = max(ans, (remain<scores.size()?-scores[0]+scores[i]:scores[i-1])+i*scores[0]+a);
       }
       dp[remain] = ans;
       return ans;
   }
   int solve(vector <int> scores) {
       dp.assign(54, -1);
       int ans = f(scores, scores.size());
       return ans;
   }

↓最初に書いた総当たりのコード

ルートだけの状態から出発して、既存ノードの次数ごとにノードを追加してヒストグラムを更新。

結構同じ状態があるんじゃないかと思ったけどそうでもなく爆発。

(↓だめな例)

class P8XGraphBuilder {
   public:
   int solve(vector <int> scores) {
       set<VI > se;
       VI a;
       a.push_back(2);
       se.insert(a);
       int ans = -100;
       int co=0;
       while(se.size()) {
           co++;
           const VI& a = *se.begin();
           //cout<<"pop "<<a<<endl;
           if(a.size()==scores.size()) {
               int lans = 0;
               REP(i, a.size()) lans+=scores[i]*a[i];
               ans=max(ans, lans);
           } else {
               REP(i, a.size()) {
                   VI b(a);
                   b.push_back(0);
                   if(b[i]>0) {
                       b[i]-=1;
                       b[i+1]+=1;
                       b[0]++;
                       //cout<<b<<endl;
                       se.insert(b);
                   }
               }
           }
           se.erase(se.begin());
       }
       cout<<co<<endl;
       return ans;