2013年湘潭大学程序设计比赛
/*B题类型：动态规划，思考由后往前，代码，由前往后。。。注意边界。。。 */ #include<iostream>#include<cstdio>#include<string>#include<cmath>using namespace std;#define manx 1009string x;int z[manx];int main(){ int n; while(cin>>n){ char s[109]; for(int i=0;i<manx;i++) z[i]=0; x.clear(); for(int i=0;i<n;i++){ cin>>s; x += s[0]; } for(int i=0;i<x.size();i++){ for(int j=i-1;j>=0;j--){ z[i]=max(z[i],z[j]); if(x[i]==x[j] && j>=1) z[i]=max(z[i],z[j-1]+1); if(x[i]==x[j] && j==0) z[i]=max(z[i],1); } } cout<<z[x.size()-1]<<endl; }}/*4shaoshanerzhongshangxiadongmen5shaoshanshangxiaertianerzhongdongmen*//*G题 类型：状态压缩搜索思路，因为状态特殊，每一个状态都可以用一个数字来代替 */#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<queue>using namespace std;#define manx 600000int flag,mark;bool s[manx];struct node{ int ans; int temp;};queue<node>que;void init(){ while(!que.empty()) que.pop(); for(int i=0;i<manx;i++) s[i]=0;}void bfs(int xx,int yy){ node te = que.front(); s[te.ans]=1; while(!que.empty()){ te=que.front(); que.pop(); // cout<<te.ans<<endl; // system("pause"); if(te.ans==mark){ flag=1; cout<<te.temp<<endl; break; } int x[2][3]; x[0][0]=te.ans/100000%10; x[0][1]=(te.ans/10000)%10; x[0][2]=(te.ans/1000)%10; x[1][0]=(te.ans/100)%10; x[1][1]=(te.ans/10)%10; x[1][2]=te.ans%10; for(int i=0;i<2;i++){ for(int j=0;j<3;j++) if(x[i][j]==0) xx=i,yy=j; } if(xx+1<2){ node qe=te; swap(x[xx][yy],x[xx+1][yy]); qe.temp++; int sum=0; for(int i=0;i<2;i++){ for(int j=0;j<3;j++){ sum=sum*10+x[i][j]; } } qe.ans=sum; if(!s[sum]) { s[sum]=1; que.push(qe); } swap(x[xx][yy],x[xx+1][yy]); } if(xx-1>=0){ node qe=te; swap(x[xx][yy],x[xx-1][yy]); qe.temp++; int sum=0; for(int i=0;i<2;i++){ for(int j=0;j<3;j++){ sum=sum*10+x[i][j]; } } qe.ans=sum; if(!s[sum]) { s[sum]=1; que.push(qe); } swap(x[xx][yy],x[xx-1][yy]); } if(yy+1<3){ node qe=te; swap(x[xx][yy],x[xx][yy+1]); qe.temp++; int sum=0; for(int i=0;i<2;i++){ for(int j=0;j<3;j++){ sum=sum*10+x[i][j]; } } qe.ans=sum; if(!s[sum]) { s[sum]=1; que.push(qe); } swap(x[xx][yy],x[xx][yy+1]); } if(yy-1>=0){ node qe=te; swap(x[xx][yy],x[xx][yy-1]); qe.temp++; int sum=0; for(int i=0;i<2;i++){ for(int j=0;j<3;j++){ sum=sum*10+x[i][j]; } } qe.ans=sum; if(!s[sum]) { s[sum]=1; que.push(qe); } swap(x[xx][yy],x[xx][yy-1]); } }}int main(){ int t; cin>>t; while(t--){ init(); int a,sum=0; flag=0; node te; int st,ed,val; for(int i=0;i<2;i++){ for(int j=0;j<3;j++){ scanf("%d",&val); if(val==0) st=i,ed=j; sum=sum*10+val; } } te.ans=sum; sum=0; for(int i=0;i<2;i++){ for(int j=0;j<3;j++){ scanf("%d",&a); sum=sum*10+a; } } mark=sum; te.temp=0; que.push(te); bfs(st,ed); if(!flag) cout<<"Impossible!"<<endl; } // while(1);}/*20 1 23 4 51 2 03 4 51 2 04 5 31 2 34 0 5*/