好贷网好贷款

TopCoder SRM 590 Div2 第3题

发布时间:2016-12-5 4:38:10 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"TopCoder SRM 590 Div2 第3题",主要涉及到TopCoder SRM 590 Div2 第3题方面的内容,对于TopCoder SRM 590 Div2 第3题感兴趣的同学可以参考一下。

类型:dp 难度:2.5 题目大意:一张图有多列,每列有'U','D','.'的排列。U表示可向上走,D表示可向下走,.表示为空,U和P不能交叉或重合,问有几种摆法 例如: ".D." "..." ".U." 有三种摆法,分别为: ".D." "..." ".U."   "..." ".D." ".U."   ".D." ".U." "..."   分析:整体思路是,算出每一列的摆法,然后依次相乘,即为结果。 而对于计算每一列的摆法,做的时候走了很多弯路,一开始有递归+枚举的办法,每一列从上往下依次遍历,对于U和D分别处理,因为U从上往下遍历即可递归计算,而D需从下往上递归计算,故看成一段U一段D的分割,分别计算。但是由于递归复杂度很高,最后超时。 后来一直想不明白,讲一个子问题请教了了大神~发现是动态规划的问题,关于子问题“序列中只含有U或D”的解法参见大神博客http://blog.csdn.net/vinson0526/article/details/11562767 最终关于此题的完整解法如下: 对于每一列,先记录每个U或P的出现位置 dp[i][j]记录第i个U或P在第j行可能出现的次数。 则递推公式为:dp[i][j] = sum(dp[i-1][k]) , 0<=k<j 即:第i个U或P在第j行可能出现的次数为第i-1个U或P在之前所有位置[0,j)可能出现次数的和 之后,若为U,则j从U出现位置向上遍历;若为D,j从D出现位置向下遍历 最外层循环再依次遍历每个U或P即可。 最后注意初始化,将第1个U或P从出现位置向上/下全部置为1   代码如下:   #include<string> #include<vector> #include<cstring> #include<map> #include<iostream> #include<algorithm> using namespace std; #define MAX(x,y) (x)>(y)?(x):(y) const int mol = 1000000007; const int MAX = 55; class FoxAndShogi { public: int row,col; map<string,int> rec; int cal(string col) { int pos[MAX][2]; memset(pos,0,sizeof(pos)); int cnt = 0; int n = col.length(); for(int i=0; i<n; i++) { if(col[i]=='U') { pos[cnt][0] = i; pos[cnt++][1] = -1; } else if(col[i]=='D') { pos[cnt][0] = i; pos[cnt++][1] = 1; } } if(cnt==0) return 1; int dp[MAX][MAX]; memset(dp,0,sizeof(dp)); for(int i=pos[0][0]; i>=0 && i<n; i+=pos[0][1]) dp[0][i] = 1; for(int i=1; i<cnt; i++) { for(int j=pos[i][0]; j>=0 && j<n; j+=pos[i][1]) for(int k=0; k<j; k++) { dp[i][j] += dp[i-1][k]; dp[i][j] %= mol; } } /* for(int i=0; i<cnt; i++) { for(int j=0; j<n; j++) cout<<dp[i][j]<<" "; cout<<endl; }*/ int ans = 0; for(int i=0; i<n; i++) { ans += dp[cnt-1][i]; ans %= mol; } return ans % mol; } int differentOutcomes(vector <string> board) { long long ans = 1; row = board.size(); col = board[0].length(); for(int j=0; j<col; j++) { string coltmp; coltmp.resize(row); for(int i=0; i<row; i++) { coltmp[i] = board[i][j]; } int cnt; if(rec[coltmp]>0) cnt = rec[coltmp]; else { cnt = cal(coltmp); rec[coltmp] = cnt; } ans = (ans * cnt) % mol; } return ans % mol; } };    

上一篇:C语言链表在笔试面试中常考问题总结
下一篇:android 休眠唤醒流程及定位唤醒问题总结

相关文章

相关评论