今天做得還算順利哈，其他的題都還蠻簡單的，就是這道G題，yy了半天，寫這個(gè)題的時(shí)候快米有時(shí)間了，最后也沒出。 后來聽yayamao說用搜索，囧了~完全沒想到，我只會(huì)用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);//這里要少排一個(gè)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;
}
順帶一提，比賽的時(shí)候 問了下zjut_DD G題的解法，他沒睬我，比賽結(jié)束后發(fā)現(xiàn) 他就這題沒殺出來。。。。
好吧，我只能說DP解法是錯(cuò)的。。。。。。
6596487788
這組數(shù)據(jù)確實(shí)過不去。。。