AT214 連射王高橋君 题解
Doveqise
2019-03-07 17:43:14
一道搜索题(跟前两道题完全不是一个难度啊QAQ)
这个搜索写到我虚(还是太虚了)
刚开始以为是背包OwO
吹爆这道题!
两遍dfs emmm...
按题意写搜索就好(才不是懒得写注释了呢)
(其实这个代码~~不~~太难看)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int num[20],len,f[15][15][95][20],ava[10],anslen=inf,anscnt;
char s[10];
long long price,pw[20],ansnum[15];
int dfs1(int cnt,int dn,int sum,int ps){
if(~f[cnt][dn][sum][ps])return f[cnt][dn][sum][ps];
if(ps>=len)return f[cnt][dn][sum][ps]=(sum==0?0:inf);
if(dn>=cnt)return f[cnt][dn][sum][ps]=(num[ps]==sum%10?dfs1(cnt,0,sum/10,ps+1):inf);
int res=inf;
for(int i=0;i<=9;i++)if(ava[i])res=min(res,dfs1(cnt,dn+1,sum+i,ps)+1);
if(dn)res=min(res,dfs1(dn,dn,sum,ps));
return f[cnt][dn][sum][ps]=res;
}//dfs找最小位数
void dfs2(int cnt,int dn,int sum,int ps){
if(ps>=len)return;
if(dn>=cnt){dfs2(cnt,0,sum/10,ps+1);return;}
int now=f[cnt][dn][sum][ps];
for(int i=0;i<=9;i++)if(ava[i]&&f[cnt][dn+1][sum+i][ps]+1==now){
ansnum[dn]+=1ll*i*pw[ps],dfs2(cnt,dn+1,sum+i,ps);return;}
dfs2(dn,dn,sum,ps);//dfs找方案
}
int main(){
scanf("%s%lld",s,&price);//读入
int leng=strlen(s);//数字个数
for(int i=0;i<=leng;i++)ava[s[i]-'0']=1;//能用的数字
while(price)num[len++]=price%10,price/=10;//price位数
memset(f,-1,sizeof(f));
for(int i=1;i<=10;i++){
int now=(i==1?0:i)+dfs1(i,0,0,0);
if(now<anslen)anslen=now,anscnt=i;//检验答案最优性
}
pw[0]=1;
for(int i=1;i<=len;i++)pw[i]=pw[i-1]*10;
dfs2(anscnt,0,0,0);if(anscnt==1)printf("%lld",ansnum[0]);
else for(int i=0;i<=anscnt-1;i++){printf("%lld",ansnum[i]);printf("%c",(i+1)==anscnt?'=':'+');}//输出
puts("");/*万恶换行*/return 0;
}
```