poj 1038

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

http://poj.org/problem?id=1038

这题我找Wrong找到想吐了。。。。本来就是看别人的代码，别人的思路写的，感觉都一模一样了，但还是Wrong。我就从别人正确的代码，一个函数一个函数的换成我的函数，wocao，怎么全部搬过来都还是AC了。。。。。。最上面怎么会有问题？？？难道头文件会Wrong？？？
哇~这要是真的的话，那我就发现了什么不得了的事了(〃’▽’〃)
结果。。。我TM的数组开小了。。。。。哎~一下午的时间(；´д｀)ゞ

#include"iostream"
#include"cstring"
#include"cmath"
using namespace std;
const int maxn=59050;
int dp[2][maxn];
int ternary[maxn][11];
int Map[151][11];
int p[11],q[11];
int N,M,K;
int all,pre,now;
int ans;int ten(int *p)//ÓÐÖÖhashµÄ¸Ðjio
{int res=0;for(int i=1; i<=M; i++)res=res*3+p[i];return res;
}
void three()
{for(int i=0; i<all; i++){int t=i;for(int j=0; j<M; j++){ternary[i][M-j]=t%3;t/=3;}}
}
void print()
{for(int i=0; i<all; i++){for(int j=1; j<=M; j++)cout<<ternary[i][j]<<" ";int t=ten(ternary[i]);cout<<"t="<<t<<"\n";cout<<"\n";}
}void dfs(int k,int nownum,int qnum)
{dp[now][qnum]=max(dp[now][qnum],nownum);ans=max(ans,nownum);for(int i=k; i<=M; i++){if(i+1<=M){if(q[i]==0&&q[i+1]==0&&p[i]==0&&p[i+1]==0)//Êú×Å·Å{q[i]=q[i+1]=2;dfs(i+2,nownum+1,ten(q));q[i]=q[i+1]=0;}}if(i+2<=M){if(p[i]<=1&&p[i+1]<=1&&p[i+2]<=1&&q[i]==0&&q[i+1]==0&&q[i+2]==0)//ºá×Å·Å{q[i]=q[i+1]=q[i+2]=2;dfs(i+3,nownum+1,ten(q));q[i]=q[i+1]=q[i+2]=0;}}}
}
int main()
{int T;cin>>T;while(T--){ans=0;cin>>N>>M>>K;all=pow(3,M);three();memset(Map,0,sizeof(Map));for(int i=1; i<=K; i++){int x,y;cin>>x>>y;Map[x][y]=1;}pre=now=1;for(int i=1; i<=M; i++){p[i]=Map[1][i]+1;//¾ÍÊÇ˵µÚÒ»ÐÐÉÏÃæûÓУ¬ËùÒÔµ±³ÉÓж«Î÷µ²×Å£¬ËùÒÔÖÁÉÙ¶¼ÊÇ1}memset(dp,-1,sizeof(dp));dp[pre][ten(p)]=0;for(int i=1; i<N; i++){now=pre^1;memset(dp[now],-1,sizeof(dp[now]));for(int sta=0; sta<all; sta++){if(dp[pre][sta]==-1)continue;for(int k=1; k<=M; k++)p[k]=ternary[sta][k];for(int k=1; k<=M; k++){if(Map[i+1][k]==1)q[k]=2;else if(p[k]==0)q[k]=0;else q[k]=p[k]-1;}dfs(1,dp[pre][sta],ten(q));}pre=now;}cout<<ans<<"\n";}
}

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

---