NOIP 2012 T2 国王游戏 （贪心+高精）

思路：

呃呃网上那么多题解写得都不错…..

就是高精 巨坑。。。

这里展出的是任氏高精（纯自己yy滴）

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,temp[5555],len,A[5555],ans[5555],ans_max;

char s[11],jya[11];

struct Node{

    char a[11];

    int alen,b;

}node[1005];

bool cmp(Node x,Node y){

    int xa=0,ya=0;

    for(int i=x.alen-1;~i;i--)xa=xa*10+x.a[i];

    for(int i=y.alen-1;~i;i--)ya=ya*10+y.a[i];

    return xa*x.b<ya*y.b;

}

int main(){

    scanf("%d",&n);

    scanf("%s%d",s,&node[0].b);

    len=strlen(s)-1;

    for(int i=0;i<=len;i++)A[i]=s[len-i]-'0';

    for(int i=1;i<=n;i++){

        scanf("%s%d",jya,&node[i].b);

        node[i].alen=strlen(jya);

        for(int j=0;j<node[i].alen;j++)

            node[i].a[j]=jya[node[i].alen-j-1]-'0';

    }

    sort(node+1,node+1+n,cmp);

    for(int i=1;i<=n;i++){

        memset(temp,0,sizeof(temp));

        int res=0,maxx=0;

        for(int j=len;~j;j--){

            res=res*10+A[j];

            temp[j]=res/node[i].b;

            if(temp[j])maxx=max(maxx,j);

            res=res%node[i].b;

        }

        for(int j=5000;~j;j--)

            if(ans[j]<temp[j]){

                for(int j=maxx;~j;j--)

                    ans[j]=temp[j];

                    ans_max=maxx;

                    break;

            }

            else if(ans[j]>temp[j])break;

        memset(temp,0,sizeof(temp));

        for(int j=0;j<=len;j++)

            for(int k=0;k<node[i].alen;k++)

                temp[j+k]+=A[j]*node[i].a[k];

        for(int j=0;j<=len+10;j++){

            temp[j+1]+=temp[j]/10;

            temp[j]=temp[j]%10;

            if(temp[j])len=j;

        }

        for(int j=len;~j;j--)A[j]=temp[j];

    }

    for(int j=ans_max;~j;j--)printf("%d",ans[j]);

}