# [FZOJ1569]&&[2014-10-28 模拟赛] 狐狸的谜语 (puzzle.*)

## 样例输入 SampleInput

57474848336869865548
167
22222222222222222222
40
33333333333333333333
60
44444444444444444444
80
55555555555555555555
250
0
-1

18
19
19
19
16

FZOJ 1569

## 代码 Code

#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;
}