<p>Given an array of integers <code>cost</code> and an integer <code>target</code>, return <em>the <strong>maximum</strong> integer you can paint under the following rules</em>:</p>

<ul>
	<li>The cost of painting a digit <code>(i + 1)</code> is given by <code>cost[i]</code> (<strong>0-indexed</strong>).</li>
	<li>The total cost used must be equal to <code>target</code>.</li>
	<li>The integer does not have <code>0</code> digits.</li>
</ul>

<p>Since the answer may be very large, return it as a string. If there is no way to paint any integer given the condition, return <code>&quot;0&quot;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> cost = [4,3,2,5,6,7,2,5,5], target = 9
<strong>Output:</strong> &quot;7772&quot;
<strong>Explanation:</strong> The cost to paint the digit &#39;7&#39; is 2, and the digit &#39;2&#39; is 3. Then cost(&quot;7772&quot;) = 2*3+ 3*1 = 9. You could also paint &quot;977&quot;, but &quot;7772&quot; is the largest number.
<strong>Digit    cost</strong>
  1  -&gt;   4
  2  -&gt;   3
  3  -&gt;   2
  4  -&gt;   5
  5  -&gt;   6
  6  -&gt;   7
  7  -&gt;   2
  8  -&gt;   5
  9  -&gt;   5
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> cost = [7,6,5,5,5,6,8,7,8], target = 12
<strong>Output:</strong> &quot;85&quot;
<strong>Explanation:</strong> The cost to paint the digit &#39;8&#39; is 7, and the digit &#39;5&#39; is 5. Then cost(&quot;85&quot;) = 7 + 5 = 12.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> cost = [2,4,6,2,4,6,4,4,4], target = 5
<strong>Output:</strong> &quot;0&quot;
<strong>Explanation:</strong> It is impossible to paint any integer with total cost equal to target.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>cost.length == 9</code></li>
	<li><code>1 &lt;= cost[i], target &lt;= 5000</code></li>
</ul>

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        map<int, int> costs;
        int max_cost = 0;
        for (int i = 0; i < 9; i++) {
            costs[cost[i]] = i;
            max_cost = max(max_cost, cost[i]);
        }
        vector<int> costvec;
        vector<int> numvec;
        for (auto& ele : costs) {
            //costvec.push_back(ele.first);
            numvec.push_back(ele.second);
        }
        sort(numvec.begin(), numvec.end());
        for (auto& ele : numvec) {
            //costvec.push_back(ele.first);
            costvec.push_back(cost[ele]);
        }
        int n_cost = costs.size();
        vector<vector<int>> dp(target+1, vector<int>(n_cost, 0));
        for (int i = 1; i <= target; i++) {
            //cout << i << endl;
            vector<int> cur(n_cost, 0);
            int n_digits_cur = 0;
            int maxx = -1;
            for (int j = 0; j < n_cost; j++) {
                if (costvec[j] == i) {
                    maxx = max(maxx, j);
                }
            }
            if (maxx != -1) {
                cur[maxx] = 1;
                n_digits_cur = 1;
            }
            for (int j = 0; j < n_cost; j++) {
                int c = costvec[j];
                if (c > i) continue;
                auto tmp = dp[i - c];
                int n_digits = 0;
                for (int k = 0; k < n_cost; k++) {
                    n_digits += tmp[k];
                }
                if (n_digits == 0) continue;
                tmp[j]++;
                if ((n_digits + 1) < n_digits_cur) continue;
                if ((n_digits + 1) > n_digits_cur) {
                    cur = tmp;
                    n_digits_cur = n_digits + 1;
                }
                else {
                    //cout << (n_digits + 1) << ' ' << n_digits_cur << endl;
                    bool cur_bigger = true;
                    for (int k = n_cost-1; k >= 0; k--) {
                        if (tmp[k] > cur[k]) {
                            cur_bigger = false;
                            break;
                        }
                        else if (tmp[k] < cur[k]) {
                            cur_bigger = true;
                            break;
                        }
                    }
                    if (!cur_bigger) {
                        cur = tmp;
                        n_digits_cur = n_digits + 1;
                    }
                }
            }
            //dp.erase(dp.begin());
            dp[i]=cur;
        }
        auto& targ = dp[target];

        string res = "";
        
        for (int i = 0; i < n_cost; i++) {
            res = string(targ[i], char(numvec[i]+'1')) + res;
        }
        if (res == "") return "0";
        return res;
    }

    bool bigger(priority_queue<int> a, priority_queue<int> b) {
        if (a.size() > b.size()) return true;
        if (a.size() < b.size()) return false;

        while (!a.empty()) {
            if (a.top() > b.top()) return true;
            if (a.top() < b.top()) return false;
            a.pop();
            b.pop();
        }
        return false;
    }
};
59228