【問(wèn)題描述】
【問(wèn)題描述】
下午，小家伙們對(duì)跳棋已經(jīng)沒(méi)有什么興趣了，大家要求老師換一個(gè)游戲，老師說(shuō)：“好玩的游戲我這還多著呢!不過(guò)就看誰(shuí)能又快又好地回答老師的問(wèn)題？”
有一個(gè)新的乘法運(yùn)算符“”，我們將它的定義為：
(XY)=X的各位數(shù)字之和×Y的最大數(shù)字+Y的最小數(shù)字
例如：（930）=9×3+0=27。
給定一個(gè)整數(shù)X和K，由X和運(yùn)算可以組成各種不同的表達(dá)式使其運(yùn)算結(jié)果為K。例如：X=3 K=7時(shí)，通過(guò)表達(dá)式：3(33)=3(3×3+3)=312=3×2+1得到，可以證明2個(gè)運(yùn)算是最少的。
現(xiàn)在老師要求計(jì)算出由X和運(yùn)算組成的值為K的表達(dá)式最少需用多少個(gè)運(yùn)算？
【數(shù)據(jù)輸入】
共1行：兩個(gè)整數(shù)X和K。
【數(shù)據(jù)輸出】
共1行：輸出最少的運(yùn)算個(gè)數(shù)，如果無(wú)法得到K，則輸出“Impossible!”（不包含雙引號(hào)）
【樣例】
cm.in cm.out
3 12 1
【數(shù)據(jù)范圍】
對(duì)100%的數(shù)據(jù)，1≤X，K≤10^20。 反復(fù)DP，和去年市賽最后一題類似。
但本題的惡心之處在于10^20
其實(shí)能生成的k的范圍是很小的，約小于2000.
同時(shí)數(shù)據(jù)讀入要用字符串，int64<10^1
代碼
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
int const maxmaxn=2000;
long long maxn;
int inline max(int a,int b)
{return a>b?a:b;}
int inline min(int a,int b){return a<b?a:b;}
int f[maxmaxn];
int a[maxmaxn];
int b[maxmaxn];
int c[maxmaxn];
int main(){
maxn=maxmaxn-20;
freopen("cm.in","r",stdin);
freopen("cm.out","w",stdout);
long long n;
long long k;
memset(f,255,sizeof(f));//-1這個(gè)原理請(qǐng)自己研究
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
scanf("%lld %lld",&n,&k);
fclose(stdin);
if(n==k){
printf("%d",0);
fclose(stdout);
return 0;
}
if(k>maxn){
printf("Impossible!");
fclose(stdout);
return 0;
}
for(int i=1;i<=maxn;i++){
int t=i;
c[i]=0x7FFFFFFF;
while(t){
int q=t%10;
a[i]+=q;
b[i]=max(b[i],q);
c[i]=min(c[i],q);
t/=10;
}
}
freopen("cm.in","r",stdin);
char s[25];
scanf("%s ",s);
c[0]=0x7FFFFFFF;
for(int i=0;i<=strlen(s)-1;i++){
int q=s[i]-'0';
a[0]+=q;
b[0]=max(b[0],q);
c[0]=min(c[0],q);
}
f[0]=0;
fclose(stdin);
for(;;){//反復(fù)DP
bool flag=true;
for(int i=0;i<=maxn;i++)
if(f[i]!=-1)
for(int j=0;j<=maxn;j++)
if(f[j]!=-1){
int t=a[i]*b[j]+c[j];
if(t>maxn||t==0)
continue;
if((f[i]+f[j]+1<f[t]&&f[t]>=0)||f[t]==-1){//松弛
f[t]=f[i]+f[j]+1;
flag=false;
}
}
if(flag){//結(jié)束
flag=false;
break;
}
}
if(f[k]!=-1)
printf("%d",f[k]);
else
printf("Impossible!");
fclose(stdout);
return 0;
}
9！！！