暴力打表+区间dp 2020 Multi-University Fragrant numbers
题目大意：
有一个字符串 (1145141919) ，它可以重复，无限变长， (114514191911451419191145141919...)
你可以取这个字符串的一个前缀，在这个前缀插入 (() ()) (+) (*) ，形成一个合法的四则运算，问最短的前缀使得四则运算的结果等于 (n)。
题解：
因为 (N<=5000) ，那么合理猜测，前面20个前缀可以组成这5000个数。
所以先打个表，判断一个前面20个数可以构成多少个5000以内的数。
直接暴力dfs不太好写，考虑区间dp来合并。
- 首先预处理直接黏在一起的部分
- 然后区间求可能的所有值，用vector存下来。
最后发现11个就可以了。。。
#include <bits/stdc++.h>
#define debug(x) cout<<"debug:"<<#x<<" = "<<x<<endl;
using namespace std;
typedef long long ll;
const int maxn = 5e3+10;
vector<int>num[110][110];
bool dp[110][110][maxn];
int vis[maxn];
int a[] = {0,1,1,4,5,1,4,1,9,1,9,1,1,4,5,1,4,1,9,1,9};
int main() {
int n = 11;
for (int len = 1; len <= 5; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1, res = 0;
for (int x = i; x <= j; x++) res = res * 10 + a[x];
if (res > 5000||dp[i][j][res]) continue;
dp[i][j][res] = true;
num[i][j].push_back(res);
}
}
for (int len = 1; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++) {
int len1 = num[i][k].size();
for (int x = 0; x < len1; x++) {
int len2 = num[k + 1][j].size();
for (int y = 0; y < len2; y++) {
int u = num[i][k][x], v = num[k + 1][j][y];
ll res = 1ll * u * v;
if (res <= 5000&&!dp[i][j][res]) {
dp[i][j][res] = true;
num[i][j].push_back(res);
}
res = u + v;
if (res <= 5000&&!dp[i][j][res]) {
dp[i][j][res] = true;
num[i][j].push_back(res);
}
}
}
}
}
}
int tot = 0;
for(int i=1;i<=5000;i++) {
for (int j = 1; j <= n; j++) {
if (dp[1][j][i] && vis[i] == 0) {
tot++,vis[i] = j;
break;
}
}
}
// debug(tot);
int T;
scanf("%d",&T);
while(T--){
int m;
scanf("%d",&m);
printf("%d
",vis[m]?vis[m]:-1);
}
}