描述 Description
话说某一个月黑风高的晚上, 一只褐色的狐狸快速地跳过了一只懒狗, 并留下一个字符串 “032089” 和一个数字 5。
这其中一定隐含了某些秘密! 酷爱思考的你马上发现，这个字符串可以写成：“03+2+0*89”，结果为 5。这是一个非常有趣的问题!
现在给出一个长度为 N 的数字字符串和一个数字 T，要求插入最少的加号或者乘号，使得数字字符串的运算结果为 T。运算符 * 号优先级高于 + 号，运算数可以有任意个前导 0。
输入格式 InputFormat
输入不超过 5 组数据, 每组数据两行。
每组数据的第 1 行为长度为 N，只包含 0~9 的数字字符串，第 2 行为一个数字 T。
输入 T<0 表示输入结束。
输出格式 OutputFormat
输出一个数字单独占一行，表示最少需要添加的运算符 (+ 号或 * 号) 数，无解输出 - 1。
样例输入 SampleInput
57474848336869865548
167
22222222222222222222
40
33333333333333333333
60
44444444444444444444
80
55555555555555555555
250
0
-1
样例输出 SampleOutput
18
19
19
19
16
代码 Code
分两步 dp，先处理只添加乘号的情况，然后在此基础上再加上加号。
预处理，用 a[i][j]表示区间 i~j 不添加符号时得到的数字，注意因为 20 位会爆 long long 所以当数字太大时直接赋值 inf 即可。。
第一步，用 f[i][j][k]表示区间 i~j 运算结果为 k 时所需添加的最少的乘号个数。则 \[ f[i,j,k]=Min\{f[i,j,k],f[i,l,\frac{k}{a[l+1,j]}]+1\} , l\in[i,j-1] , a[l+1,j] | k \]
第二步，用 g[i][j]表示前 i 个数字运算结果为 j 时所需要添加的最少符号个数。则 \[ g[i,j]=Min\{f[0,i,j],g[k,l]+f[k+1,i,j-l]+1\} , k\in[1,i-1] , l\in[0,j] \]
最终答案为 g[n][t].
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
const ll int_inf=0x7fffffff;
const ll inf=int_inf*int_inf;
ll i,j,t,n,m,l,r,k,z,y,x;
ll a[25][25],f[25][25][255],g[25][255];
char ch[25];
inline ll convert(ll l,ll r)
{
ll i,j,t=0;
if (r-l>15) return inf;
for (i=l;i<=r;i++) t=t*10+ch[i]-'0';
return t;
}
int main()
{
scanf("%s",ch);
scanf("%lld",&t);
while (t>=0)
{
n=strlen(ch);
for (i=0;i<n;i++) for (j=i;j<n;j++) a[i+1][j+1]=convert(i,j);
for (i=1;i<=n;i++) for (j=1;j<=n;j++) for (k=0;k<=t;k++) f[i][j][k]=inf;
for (i=1;i<=n;i++) if (a[i][i]==0)
{
for (j=1;j<i;j++) f[j][i][0]=1;
for (j=i+1;j<=i;j++) f[i][j][0]=1,f[1][j][0]=2;
}
for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (a[i][j]<=t) f[i][j][a[i][j]]=0;
for (i=1;i<=n;i++) for (j=i;j<=n;j++) for (k=0;k<=t;k++)
{
for (l=i;l<j;l++) if (a[l+1][j] && k%a[l+1][j]==0) f[i][j][k]=min(f[i][j][k],f[i][l][k/a[l+1][j]]+1);
}
for (i=1;i<=n;i++) for (j=0;j<=t;j++) g[i][j]=f[1][i][j];
for (i=1;i<=n;i++) for (j=0;j<=t;j++)
{
for (k=1;k<i;k++) for (l=0;l<=j;l++) g[i][j]=min(g[i][j],g[k][l]+f[k+1][i][j-l]+1);
}
printf("%lld\n",(g[n][t]==inf)?-1:g[n][t]);
scanf("%s",ch);
scanf("%lld",&t);
}
return 0;
}