SRM311 div2 medium

変則的な動的計画法の問題．問題の趣向から、iを逆順に回して最大値を簡単に取得できるようにしている．
また、j++とすることで、暗に数字を複数回使ってよいことを表している．

もし、
for(int j = n; j >= matches[i]; j--) {
  ...
}
としてみると、数字は一回しか使われないことが分かる．

/* これはまずい．stringの長さが20とかだったらintがoverflowをおこしてしまう。
結果が代わってくるので、stringのまま処理しなければならない．
string maxToInt(string a, string b) {
  if(a == "" || b == "") {
    return (a == "") ? b : a;
  }
  int numa; int numb;
  sscanf(a.c_str(), "%d", &numa);
  sscanf(b.c_str(), "%d", &numb);
  return (numa > numb) ? a : b;
}
*/
//これなら、stringがどんな長さでも数字順に並ぶ．
string maxToInt(string a, string b) {
  string ans = "";
  int lena = a.length(); int lenb = b.length();
  if(lena > lenb) ans = a;
  else if(lena < lenb) ans = b;
  else ans = (a > b) ? a : b;
  return ans;
}

class MatchNumbersEasy {
public:
  string maxNumber(vector <int> matches, int n) {
    int sz = matches.size();
    string dp[51][51]; //dp[sz+1][n+1]
    fill(dp[0], dp[0]+51*51, "");
    for(int i = sz-1; i >= 0; i--) { 
      for(int j = matches[i]; j <= n; j++) {
	char ch = i + '0';
	dp[i][j] = max(dp[i][j-matches[i] ] + ch, dp[i+1][j]);
      }
    }
    return dp[0][n];    
  }