今天做得还算顺利哈，其他的题都还蛮简单的，就是这道G题，yy了半天，写这个题的时候快米有时间了，最后也没出。 后来听yayamao说用搜索，囧了~完全没想到，我只会用DP，呵呵。代码奉上。
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[1010][10];
int pre[1010][10];
char s[1010];
int a[1010];
int n;
bool check()
{
int i;
for(i=1;i<=n;i++)
{
if(a[i]==0||a[i]==5)
return true;
}
return false;
}
void init()
{
memset(dp,-1,sizeof(dp));
int i;
for(i=1;i<=n;i++)
a[i]=s[i]-'0';
}
int get5()
{
int i;
for(i=n;i>=1;i--)
{
if(a[i]==5)
return i;
}
}
int get0()
{
int res=0;
int i;
for(i=n;i>=0;i--)
{
if(a[i]==0)
res++;
}
return res;
}
int re[2000];
bool CheckAllZero(int n)
{
int i;
for(i=1;i<=n;i++)
{
if(re[i]!=0)
return false;
}
return true;
}
int main()
{
int t;
int i,j,k;
scanf("%d",&t);
while(t--)
{
scanf("%s",s+1);
n=strlen(s+1);
init();
sort(a+1,a+1+n);
reverse(a+1,a+1+n);
if(check()==false)
{
printf("impossible\n");
continue;
}
if(a[n]==0)
{
dp[0][0]=1;
for(i=1;i<=n;i++)
{
for(j=i-1;j>=0;j--)
{
for(k=9;k>=0;k--)
{
//if(j==1&&k==7)
// __asm int 3;
if(dp[j][k]==1&&dp[j+1][(k+a[i])%9]==-1)
{
dp[j+1][(k+a[i])%9]=1;
pre[j+1][(k+a[i])%9]=a[i];
}
}
}
}
int f=0;
int nn;
for(i=1000;i>=1;i--)
{
if(dp[i][0]==1)
{
nn=i;
break;
}
}
re[i]=pre[i][0];
int t1=nn;
int t2=0;
for(j=nn-1;j>=1;j--)
{
t1--;
t2=(t2-pre[j+1][t2]+9)%9;
re[j]=pre[t1][t2];
}
if(CheckAllZero(nn))
{
printf("0\n");
continue;
}
for(i=1;i<=nn;i++)
printf("%d",re[i]);
printf("\n");
}
else
{
int t=get5();
swap(a[t],a[n]);
sort(a+1,a+n);//这里要少排一个5
dp[0][0]=1;
for(i=1;i<n;i++)
{
for(j=i-1;j>=0;j--)
{
for(k=9;k>=0;k--)
{
if(dp[j][k]==1&&dp[j+1][(k+a[i])%9]==-1)
{
dp[j+1][(k+a[i])%9]=1;
pre[j+1][(k+a[i])%9]=a[i];
}
}
}
}
int f=0;
int nn;
for(i=1000;i>=1;i--)
{
if(dp[i][0]==1)
{
f=1;
nn=i;
break;
}
}
if(f==0)
printf("impossible\n");
if(f==1)
{
re[i]=pre[i][0];
int t1=nn;
int t2=0;
for(j=nn-1;j>=1;j--)
{
t1--;
t2=(t2-pre[j+1][t2]+9)%9;
re[j]=pre[t1][t2];
}
}
for(i=1;i<=nn;i++)
printf("%d",re[i]);
printf("\n");
}
}
return 0;
}
顺带一提，比赛的时候 问了下zjut_DD G题的解法，他没睬我，比赛结束后发现 他就这题没杀出来。。。。
好吧，我只能说DP解法是错的。。。。。。
6596487788
这组数据确实过不去。。。