1 /*By SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 int read(){ 9 int x=0,f=1;char ch=getchar(); 10 while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 12 return x*f; 13 } 14 int m; 15 char n[120]; 16 struct number{ 17 int a[300]; 18 int len; 19 }a,b; 20 number operator + (number a,number b){ 21 int len=max(a.len,b.len); 22 number c={0};c.len=len; 23 int tmp=0; 24 for(int i=1;i<=len+1;i++){ 25 c.a[i]=a.a[i]+b.a[i]+tmp; 26 tmp=c.a[i]/m; 27 c.a[i]%=m; 28 } 29 if(c.a[c.len+1])c.len++; 30 return c; 31 } 32 bool pd(number x){ 33 for(int i=1;i<=x.len/2;i++){ 34 if(x.a[i]!=x.a[x.len-i+1])return 0; 35 } 36 return 1; 37 } 38 int main(){ 39 int step=0; 40 scanf("%d",&m); 41 scanf("%s",n); 42 int i,j; 43 int slen=strlen(n); 44 for(i=0;i<slen;i++){ 45 a.len=i+1; 46 if(n[slen-i-1]>='0' && n[slen-i-1]<='9') 47 a.a[i+1]=n[slen-i-1]-'0'; 48 else a.a[i+1]=n[slen-i-1]-'A'+10; 49 } 50 while(step<=30){ 51 if(pd(a)){ 52 printf("STEP=%d ",step); 53 return 0; 54 } 55 number b={0}; 56 b.len=a.len; 57 for(i=1;i<=b.len;i++) 58 b.a[i]=a.a[a.len-i+1]; 59 a=a+b; 60 step++; 61 } 62 printf("Impossible! "); 63 return 0; 64 }
数据范围太小了，所以偷了懒，各种优化都没加
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=200; 9 int h[mxn]; 10 int ans=0; 11 int f[mxn],cnt; 12 int n=0; 13 int main(){ 14 while(scanf("%d",&h[n+1])!=EOF ) ++n; 15 int i,j; 16 for(i=1;i<=n;i++)f[i]=1; 17 for(i=1;i<=n;i++) 18 for(j=1;j<i;j++) 19 if(h[j]>=h[i])f[i]=max(f[i],f[j]+1); 20 ans=0; 21 for(i=1;i<=n;i++) ans=max(ans,f[i]); 22 printf("%d ",ans); 23 //part 2 24 ans=cnt=0; 25 memset(f,0,sizeof f); 26 for(i=1;i<=n;i++){ 27 int mini=0x3f3f3f3f,pos=0; 28 for(j=1;j<=cnt;j++){ 29 if(f[j]>h[i] && f[j]<mini){ 30 mini=f[j]; 31 pos=j; 32 } 33 } 34 if(!pos){f[++cnt]=h[i];continue;} 35 f[pos]=h[i]; 36 } 37 printf("%d ",cnt); 38 return 0; 39 }
DP+搜索 这思路挺神的
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<map> 8 using namespace std; 9 const int mxn=1000; 10 int m,k; 11 int a[mxn],cnt=0; 12 bool vis[mxn]; 13 int f[mxn]; 14 int mxans=0; 15 int ans[mxn]; 16 int DFS(int pos){ 17 memset(f,0,sizeof f); 18 int i,j; 19 for(i=1;i<=2000;i++){ 20 f[i]=0x3f3f3f3f; 21 for(j=1;j<=pos;j++){ 22 if(a[j]>i)continue; 23 f[i]=min(f[i],f[i-a[j]]+1); 24 } 25 if(f[i]>m)return i; 26 } 27 } 28 void dp(int pos){ 29 int tmp=DFS(pos); 30 // printf("tmp:%d pos:%d ",tmp,pos); 31 if(tmp>mxans){ 32 mxans=tmp; 33 cnt=pos; 34 memcpy(ans,a,sizeof ans); 35 } 36 if(pos==k)return; 37 for(int i=tmp;i>a[pos];i--){ 38 a[pos+1]=i; 39 dp(pos+1); 40 } 41 return; 42 } 43 int main(){ 44 scanf("%d%d",&m,&k); 45 int i,j; 46 a[1]=1;cnt=1; 47 dp(cnt); 48 for(i=1;i<=cnt;i++){ 49 printf("%d ",ans[i]); 50 } 51 printf(" MAX=%d ",mxans-1); 52 return 0; 53 }