cafelier@SRM

SRM Member Pilot 2 900

あとで | 14:06 |

tsukunoさんにおしえてもらった。十分シンプルなダイナミック計画法であった…。

class PrefixFreeCode { public:
   int solve(int N, const vector<int>& C)
   {
      // The best way to assign N codes to the codetree
      // whose root edges are C[i..$].
      //   special cases:
      //      n==1 && i==0 => cost 0 (assign to the root)
      //      n==0         => cost 0
      //      n==0 && i==$ => cost 0 (for this, allocate C.size()+1 as sentinels)

      vector< vector<int> > dp(N+1, vector<int>(C.size()+1, 0));
      for(int n=1; n<=N; ++n)
         for(int i=(n==1 ? 1 : 0); i<C.size(); ++i)
         {
            const int at_least = (i==C.size()-1 ? n : 1);
            const int at_most  = (i==0 ? n-1 : n);

            int result = INT_MAX;
            for(int k=at_least; k<=at_most; ++k)
               result = min(result, dp[k][0]+C[i]*k + dp[n-k][i+1]);
            dp[n][i] = result;
         }
      return dp[N][0];
   }

   int minCost(int N, vector <int> characterCosts) 
   {
      sort(characterCosts.begin(), characterCosts.end());
      return solve(N, characterCosts);
   }
};