【問題解】洛谷P 1080キングゲーム[NOIP 2012 Day 1 T 2]欲張り
5683 ワード
タイトルリンクは各大臣の左右の手の上の数の積によって小さいから大きいまで並べ替えて、最良の列の方案は摂動の証明を使うことができて、詳しく李煜東のアルゴリズムの競争の進級のガイドラインを参照します
#include
#include
#include
using namespace std;
struct node{
int a,b,c;
}q[2000];
int a1[2000],b1[2000],c1[2000];
void mul(int a1[],int x){
int j=0,i,t;
for(i=1;i<=a1[0]||j;i++){
t=a1[i]*x+j;
j=t/10000;
a1[i]=t%10000;
}
a1[0]=i-1;
}
void div(int a1[],int x){
int i,j=0,t;
for(i=a1[0];i>=1;i--){
t=a1[i]+j*10000;
b1[i]=t/x;
j=t%x;
}
for(i=a1[0];i>=1;i--)if(b1[i]!=0)break;
if(i==0)b1[0]=1;
else b1[0]=i;
}
int cmp(const node&x,const node&y){
return x.c<y.c;
}
int cmp1(int b1[],int a1[]){
if(b1[0]!=a1[0])return b1[0]-a1[0];
for(int i=b1[0];i>=1;i--)
if(b1[i]!=a1[i])return b1[i]-a1[i];
return 0;
}
int main(){
//freopen("testdata.in","r",stdin);
memset(c1,0,sizeof(c1));
int i,n,a,b;
scanf("%d%d%d",&n,&a,&b);
for(i=1;i<=n;i++){
scanf("%d%d",&q[i].a,&q[i].b);
q[i].c=q[i].a*q[i].b;
}
sort(q+1,q+1+n,cmp);
a1[0]=1;a1[1]=a;c1[0]=1;
for(i=1;i<=n;i++){
div(a1,q[i].b);
if(cmp1(b1,c1)>0)
memcpy(c1,b1,(b1[0]+1)*sizeof(int));
mul(a1,q[i].a);
}
printf("%d",c1[c1[0]]);
for(i=c1[0]-1;i>=1;i--)
printf("%04d",c1[i]);
printf("
");
return 0;
}