The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

福大校赛 G题 小小的悲剧哈

今天做得还算顺利哈,其他的题都还蛮简单的,就是这道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
这组数据确实过不去。。。

posted on 2010-04-25 17:38 abilitytao 阅读(954) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理