zoj 1227

本文主要是介绍zoj 1227，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

自己的顺序DP居然超时，不得其解。拿别人代码学习之。

#include <iostream> #include <vector> #include <queue> using namespace std; bool mark[41][41][41][41]; struct node { int pair; int sq; int index[4]; int size; }; int map[41][4]; queue <node> q; int main() { int i,j,k,m,candy,mx; node ss,tt; while(cin>>m&&m!=0) { mx=0; for(i=1;i<=m;i++) for(j=0;j<4;j++) cin>>map[i][j]; memset(mark,0,sizeof(mark)); ss.pair=0; ss.sq=0; ss.size=0; for(i=0;i<4;i++) ss.index[i]=0; q.push(ss); while(!q.empty()) { ss=q.front(); q.pop(); mx=max(mx,ss.pair); for(i=0;i<4;i++) { tt=ss; tt.index[i]++; if(tt.index[i]>m) continue; if(mark[tt.index[0]][tt.index[1]][tt.index[2]][tt.index[3]]) continue; candy=map[tt.index[i]][i]; if((ss.sq>>candy)&1)//有pair { tt.pair++; tt.size-=1; tt.sq^=1<<candy; } else { tt.sq|=1<<candy; ++tt.size;} if(tt.size>=5) continue; mark[tt.index[0]][tt.index[1]][tt.index[2]][tt.index[3]]=true; q.push(tt); } } cout<<mx<<endl; } return 0; }  

#include <iostream> #include <vector> #include <queue> using namespace std; bool mark[41][41][41][41]; struct node { int pair; vector <int> q; vector <int> p; int index[4]; }; int map[41][4]; queue <node> q; int main() { //freopen("debug//in.txt","r",stdin); int i,j,k,m,candy,mx; node ss,tt; while(cin>>m&&m!=0) { mx=0; for(i=1;i<=m;i++) for(j=0;j<4;j++) cin>>map[i][j]; memset(mark,0,sizeof(mark)); ss.pair=0; ss.p.clear(); ss.q.clear(); for(i=0;i<4;i++) ss.index[i]=0; while(!q.empty()) q.pop(); q.push(ss); while(!q.empty()) { ss=q.front(); q.pop(); ss.q.clear(); mx=max(mx,ss.pair); for(i=0;i<4;i++) { tt=ss; tt.index[i]++; if(tt.index[i]>m) continue; if(mark[tt.index[0]][tt.index[1]][tt.index[2]][tt.index[3]]) continue; candy=map[tt.index[i]][i]; if(tt.p.size()!=0) { for(j=0;j<tt.p.size();j++) if(tt.p[j]==candy) break; if(j<tt.p.size())//有pair { tt.pair++; k=tt.p.size()-j-1; while(k--) { tt.q.push_back(tt.p[tt.p.size()-1]); tt.p.pop_back(); } tt.p.pop_back(); for(j=0;j<tt.q.size();j++) tt.p.push_back(tt.q[j]); tt.q.clear(); } else tt.p.push_back(candy); } else tt.p.push_back(candy); if(tt.p.size()>=5) continue; mark[tt.index[0]][tt.index[1]][tt.index[2]][tt.index[3]]=true; q.push(tt); } } cout<<mx<<endl; } return 0; }  

这个是我同学的，很有可能成为牛呀。

#include <stdio.h> #include <memory.h> int c[40][4] ; char memo[41][41][41][41] ; int h ; int pop(unsigned int x) { x = x-((x>>1)&0x55555555) ; x = (x&0x33333333) + ((x>>2) & 0x33333333 ) ; x = (x+(x>>4)) & 0x0f0f0f0f ; x = x + (x>>8) ; x = x + (x>>16) ; return x & 0x0000003f ; } int dfs (int b[] , unsigned int hand) { if (memo[b[0]][b[1]][b[2]][b[3]]) return (memo[b[0]][b[1]][b[2]][b[3]]-'0') ; int i , j , add , cur ; if (pop(hand)>=5) return 0 ; int max=0; for (i=0 ; i<4 ; i++) { if (b[i]>=h) continue ; int bex[4] ; for (j=0 ; j<4 ; j++) bex[j] = b[j] ; unsigned int handex = hand ; if ((1<<c[b[i]][i])&hand) add = 1 ; else add = 0 ; handex ^= (1<<c[b[i]][i]) ; bex[i]++ ; cur = add + dfs(bex,handex) ; if(cur>max) max=cur; } memo[b[0]][b[1]][b[2]][b[3]] = (max+'0') ; return max ; } int main () { while (scanf("%d",&h)&&h) { int i , j ; for (i=0 ; i<h ; i++) for (j=0 ; j<4 ; j++) scanf("%d",&c[i][j]); memset(memo,0,sizeof(memo)) ; int b[4] = {0} ; unsigned int hand = 0 ; printf("%d/n",dfs(b,hand)); } return 0 ; }  

这篇关于zoj 1227的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---