[ABC118D] Match Matching 题解
xvl_
·
·
题解
题目传送门
一道 dp 题。
在 dp 之前，我们需要明确以下几个东西：
状态的表示，状态转移方程，边界条件跟答案的表示。
状态的表示
### 状态转移方程
$$dp_i = \max\{j \times 10^{len(dp_{i-w_j})} + dp_{i-w_j}\}$$
其中 $len(n)$ 表示 $n$ 的位数，$w_i$ 表示拼出数字 $i$ 所需的火柴数量。实际上这里是将 $dp_{i-w_j}$ 拼在 $j$ 后面。
### 边界条件
$$dp_i = 0$$
### 答案的表示
$$dp_n$$
### Code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll n, m;
ll w[10] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
string dp[10005];
bool vis[10];
string strmax(string x, string y) {
if (x.size() > y.size()) return x;
if (x.size() < y.size()) return y;
for (int i = 0; i < x.size(); i++) {
if (x[i] < y[i]) return y;
if (y[i] < x[i]) return x;
}
}
ll sum(string s) {
ll res = 0;
for (int i = 0; i < s.size(); i++) res += w[s[i] - '0'];
return res;
}
int main() {
ios :: sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
ll x;
cin >> x;
vis[x] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 9; j++) {
if (vis[j] and i >= w[j] and sum(to_string(j) + dp[i - w[j]]) == i) dp[i] = strmax(dp[i], to_string(j) + dp[i - w[j]]);
}
}
cout << dp[n];
return 0;
}
```