[NOIP1999] 普及组

回文数

 /*By SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int m;

 char n[];

 struct number{

     int a[];

     int len;

 }a,b;

 number operator + (number a,number b){

     int len=max(a.len,b.len);

     number c={};c.len=len;

     int tmp=;

     for(int i=;i<=len+;i++){

         c.a[i]=a.a[i]+b.a[i]+tmp;

         tmp=c.a[i]/m;

         c.a[i]%=m;

     }

     if(c.a[c.len+])c.len++;

     return c;

 }

 bool pd(number x){

     for(int i=;i<=x.len/;i++){

         if(x.a[i]!=x.a[x.len-i+])return ;

     }

     return ;

 }

 int main(){

     int step=;

     scanf("%d",&m);

     scanf("%s",n);

     int i,j;

     int slen=strlen(n);

     for(i=;i<slen;i++){

         a.len=i+;

         if(n[slen-i-]>='' && n[slen-i-]<='')

             a.a[i+]=n[slen-i-]-'';

         else a.a[i+]=n[slen-i-]-'A'+;

     }

     while(step<=){

         if(pd(a)){

             printf("STEP=%d\n",step);

             return ;

         }

         number b={};

         b.len=a.len;

         for(i=;i<=b.len;i++)

             b.a[i]=a.a[a.len-i+];

         a=a+b;

         step++;

     }

     printf("Impossible!\n");

     return ;

 }

回文数

导弹拦截

数据范围太小了，所以偷了懒，各种优化都没加

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 const int mxn=;

 int h[mxn];

 int ans=;

 int f[mxn],cnt;

 int n=;

 int main(){

     while(scanf("%d",&h[n+])!=EOF ) ++n;

     int i,j;

     for(i=;i<=n;i++)f[i]=;

     for(i=;i<=n;i++)

         for(j=;j<i;j++)

             if(h[j]>=h[i])f[i]=max(f[i],f[j]+);

     ans=;

     for(i=;i<=n;i++) ans=max(ans,f[i]);

     printf("%d\n",ans);

     //part 2

     ans=cnt=;

     memset(f,,sizeof f);

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

         int mini=0x3f3f3f3f,pos=;

         for(j=;j<=cnt;j++){

             if(f[j]>h[i] && f[j]<mini){

                 mini=f[j];

                 pos=j;

             }

         }

         if(!pos){f[++cnt]=h[i];continue;}

         f[pos]=h[i];

     }

     printf("%d\n",cnt);

     return ;

 }

导弹拦截

邮票面值设计

DP+搜索这思路挺神的

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<map>

 using namespace std;

 const int mxn=;

 int m,k;

 int a[mxn],cnt=;

 bool vis[mxn];

 int f[mxn];

 int mxans=;

 int ans[mxn];

 int DFS(int pos){

     memset(f,,sizeof f);

     int i,j;

     for(i=;i<=;i++){

         f[i]=0x3f3f3f3f;

         for(j=;j<=pos;j++){

             if(a[j]>i)continue;

             f[i]=min(f[i],f[i-a[j]]+);

         }

         if(f[i]>m)return i;

     }

 }

 void dp(int pos){

     int tmp=DFS(pos);

 //    printf("tmp:%d  pos:%d\n",tmp,pos);

     if(tmp>mxans){

         mxans=tmp;

         cnt=pos;

         memcpy(ans,a,sizeof ans);

     }

     if(pos==k)return;

     for(int i=tmp;i>a[pos];i--){

         a[pos+]=i;

         dp(pos+);

     }

     return;

 }

 int main(){

     scanf("%d%d",&m,&k);

     int i,j;

     a[]=;cnt=;

     dp(cnt);

     for(i=;i<=cnt;i++){

         printf("%d ",ans[i]);

     }

     printf("\nMAX=%d\n",mxans-);

     return ;

 }