五月份做的吧 那個(gè)時(shí)候用了dp 死活過(guò)不了 后來(lái)聽(tīng)人說(shuō)dp是可行的 但我還是不會(huì)，囧。。。這題用了比較快的廣搜算法，用v[i][j][k]存儲(chǔ)余數(shù)從i->j,去掉數(shù)字為k的情況，由于狀態(tài)空間<1000，所以窮搜狀態(tài)空間是可行的。這題具體來(lái)說(shuō)可以分成三種情況：
1.字符串中既沒(méi)有5也沒(méi)有0，那么可以直接impossble掉
2.如果字符串中有5但是沒(méi)有0，可以先去掉一個(gè)5，然后在窮搜，最后在末尾添加上。
3.其他情況，只要有0，末尾一定是0。
代碼如下：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
struct node
{
int num[10];
int r;
}q[1010];
int getd(int num[])//統(tǒng)計(jì)這個(gè)大數(shù)的位數(shù)
{
int ans=0;
for(int i=0;i<10;i++)
{
ans+=num[i];
}
return ans;
}
int getsum(int num[])//統(tǒng)計(jì)這個(gè)大數(shù)每位之和
{
int ans=0;
for(int i=0;i<10;i++)
{
ans+=num[i]*i;
}
return ans;
}
int v[11][11][11];//hash判重
int num[10];//初始大數(shù)
int flagnum[10];
char s[2000];//字符串
int t;
bool haszero;//有0嗎？
bool hasfive;//有5嗎？
int ansnum[10];//最終結(jié)果，有中間處理，注意加0加5的情況
int ansflag;
int cmp(int ansnum[],int num[])
{
int len1=getd(ansnum);
int len2=getd(num);
//特別處理一下兩個(gè)數(shù)是全0的情況
if(getsum(ansnum)==0&&getsum(num)==0)
return 0;
else if(getsum(ansnum)==0&&getsum(num)!=0)
return -1;
else if(getsum(ansnum)!=0&&getsum(num)==0)
return 1;
//end
if(len1>len2)
return 1;
else if(len1<len2)
return -1;
else
{
int i;
for(i=9;i>=1;i--)
{
if(ansnum[i]>num[i])
return 1;
else if(ansnum[i]<num[i])
return -1;
}
return 0;
}
}
void copy(int t[],int s[])//copy s里面的東西到t
{
int i;
for(i=0;i<=9;i++)
t[i]=s[i];
}
void input()//從1開(kāi)始存儲(chǔ)
{
ansflag=0;
hasfive=haszero=0;
scanf("%s",s+1);
memset(ansnum,0,sizeof(ansnum));
memset(num,0,sizeof(num));
memset(v,0,sizeof(v));
int i;
int len=strlen(s+1);
for(i=1;i<=len;i++)
{
int tt=(s[i]-'0');
num[tt]++;
if(tt==0)
haszero=1;
if(tt==5)
hasfive=1;
}
}
void output(int num[])//沒(méi)有加回車(chē),注意預(yù)先去掉的數(shù)字
{
for(int i=9;i>=0;i--)
{
if(num[i]!=0)
for(int j=1;j<=num[i];j++)
printf("%d",i);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
input();
if(!haszero&&!hasfive)
{
printf("impossible\n");
continue;
}
/**//*
if(haszero&&!hasfive)
{
int l,r;
l=r=1;
copy(q[1].num,num);
int tem=getsum(q[1].num);
tem%=9;
q[1].r=tem%9;
v[tem][tem][0]=1;
while(l<=r)
{
if(cmp(q[l].num,ansnum)==1&&q[l].r==0)
{
ansflag=1;
copy(ansnum,q[l].num);
}
for(int i=1;i<10;i++)
{
int nr=(q[l].r-i+9)%9;
if(q[l].num[i]>0&&v[q[l].r][nr][i]==0)
{
r++;
copy(q[r].num,q[l].num);
q[r].num[i]--;
q[r].r=nr;
v[q[l].r][nr][i]=1;
}
}
l++;
}
if(ansflag==1)
{
output(ansnum);
printf("\n");
}
else
printf("0\n");
}
*/
else if(!haszero&&hasfive)//沒(méi)有0但是有5
{
int l,r;
l=r=1;
copy(q[1].num,num);
q[1].num[5]--;
int tem=getsum(q[1].num);
q[1].r=tem%9;
tem%=9;
v[tem][tem][0]=1;
while(l<=r)
{
if(cmp(q[l].num,ansnum)==1&&q[l].r==4)
{
ansflag=1;
copy(ansnum,q[l].num);
}
for(int i=1;i<10;i++)
{
/**//*
if(i==5)
{
__asm
{
int 3;
}
}
*/
int nr=(q[l].r-i+9)%9;
if(q[l].num[i]>0&&v[q[l].r][nr][i]==0)
{
r++;
copy(q[r].num,q[l].num);
q[r].num[i]--;
q[r].r=nr;
v[q[l].r][nr][i]=1;
}
}
l++;
}
if(ansflag==1)
{
output(ansnum);
printf("5\n");
}
else
printf("impossible\n");
}
else //沒(méi)有0但是有5或者有0有5，情況相同
{
int l,r;
l=r=1;
copy(q[1].num,num);
int tem=getsum(q[1].num);
tem%=9;
q[1].r=tem%9;
v[tem][tem][0]=1;
while(l<=r)
{
if(cmp(q[l].num,ansnum)==1&&q[l].r==0)
{
ansflag=1;
copy(ansnum,q[l].num);
}
for(int i=1;i<10;i++)
{
int nr=(q[l].r-i+9)%9;
if(q[l].num[i]>0&&v[q[l].r][nr][i]==0)
{
r++;
copy(q[r].num,q[l].num);
q[r].num[i]--;
q[r].r=nr;
v[q[l].r][nr][i]=1;
}
}
l++;
}
if(ansflag==1)
{
output(ansnum);
printf("\n");
}
else
printf("0\n");
}
}
return 0;
}
代碼寫(xiě)的比較長(zhǎng)比較猥瑣，不知道能把幾個(gè)廣搜合并下么。
感謝messidou神牛指點(diǎn)。