南昌邀请赛网络赛 D.Match Stick Game
每一个字符都是由若干个火柴棒构成的，我们可以考虑类似于背包的思路来求解。
因为每个数的位数最后都没发生变化，所以我们可以预处理出\(f[i][j]\)以及\(g[i][j]\)，分别表示\(i\)位数由\(j\)根火柴构成的最大/最小值。
因为这里除开火柴棒个数之外还涉及到了加减号，所以我们定义\(dp(i,j,0/1)\)为前\(i\)个数字，用了\(j\)根火柴棒，并且当前这个数字前面是\(-\)还是\(+\)。
由于数据范围比较小，所以考虑加和减两种情况进行合理转移就行了。
详见代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
int n, T;
char s[N] ;
int len[N] ;
ll dp[105][N][2], f[105][N], g[105][N];
int trans1[10] = {0, 0, 1, 7, 4, 5, 9, 8} ;
int trans2[10] = {0, 0, 1, 7, 4, 2, 0, 8} ;
int num ;
int main() {
cin >> T;
for(int i = 1; i <= 10; i++)
for(int j = 2; j < N; j++) {
g[i][j] = 1e14;
f[i][j] = f[i][j - 1] ;
for(int k = 2; k <= 7; k++) {
if(j - k >= 0) f[i][j] = max(f[i - 1][j - k] * 10 + trans1[k], f[i][j]) ;
}
}
for(int i = 1; i <= 10; i++)
for(int j = 2; j < N; j++) {
if(i == 1) {
g[i][j] = 1;
continue ;
}
g[i][j] = g[i][j - 1] ;
for(int k = 2; k <= 7; k++) {
if(j - k >= 0) g[i][j] = min(1ll * g[i - 1][j - k] * 10 + 1ll * trans2[k], g[i][j]) ;
}
}
while(T--) {
memset(dp, 0, sizeof(dp)) ;
scanf("%d", &n);
scanf("%s", s + 1);
int cnt = 0, x = 0, num = 0;
for(int i = 1; i <= n; i++) {
if(s[i] == '+' || s[i] == '-') {
len[++num] = cnt ;
cnt = 0;
if(s[i] == '+') x += 2;
else x += 1;
} else {
cnt++;
if(s[i] == '1') x += 2 ;
else if(s[i] == '7') x += 3 ;
else if(s[i] == '4') x += 4 ;
else if(s[i] == '5' || s[i] == '2' || s[i] == '3') x += 5;
else if(s[i] == '0' || s[i] == '6' || s[i] == '9') x += 6;
else x += 7;
}
}
len[++num] = cnt;
for(int i = 2; i <= x; i++) dp[1][i][0] = dp[1][i][1] = f[len[1]][i] ;
for(int i = 2; i <= num; i++) {
for(int j = 2; j <= x; j++) {
for(int k = 2; k <= j; k++) {
if(j - k - 2 >= 2) {
dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - k - 2][1] + f[len[i]][k]) ;
dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - k - 2][0] + f[len[i]][k]) ;
}
if(j - k - 1 >= 2) {
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - k - 1][0] - g[len[i]][k]) ;
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - k - 1][1] - g[len[i]][k]) ;
}
}
}
}
ll ans = 0;
ans = max(ans, max(dp[num][x][0], dp[num][x][1])) ;
cout << ans << '\n';
}
return 0 ;
}