[ABC118D] Match Matching

题目传送门

引

题目的描述很形象，梦回童年，注意一下火柴全部都用完

解法

显然 DP ,

设计状态：

$$f_i:用完i根木棒凑出的最大数$$

状态转移：

$$f_i\to f_{i+cn{t}_j}即枚举下一个加入的数j,取\max$$

Code ：

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int N=1e4+10;
int n,m;
int cnt[]={0,2,5,5,4,5,6,3,7,6};
string f[N];
vector<int> num;
int main() {scanf("%d%d",&n,&m);for(int i=1,x;i<=m;i++) {scanf("%d",&x);num.push_back(x);}for(int i=0;i<n;i++) {for(int x:num) {if(i && f[i].empty()) continue;string s1=f[i]+char(x+'0'),s2=char(x+'0')+f[i],tmp="";tmp=(s1>s2)?s1:s2;if(tmp.size()>f[i+cnt[x]].size()) f[i+cnt[x]]=tmp;else if(tmp.size()==f[i+cnt[x]].size()) f[i+cnt[x]]=max(tmp,f[i+cnt[x]]);}}cout<<f[n]<<'\n';
}