思路
1. 读完题, 感觉这是道 DP 题
2. 前几天做了一道统计括号数的题目, 和此题比较类似
3. dp[i][j] 表示前 i 个人中有 j 个女生的方案数, 那么状态转移方程就能写为
dp[i][j] = dp[i-1][j] (最后一位放男生) + dp[i-2][j-2] (最后一位放女生, 那么倒数第二位必须是女生)
4. 初始化 dp[i][0] = 1, dp[i][1] = 0. 但要考虑例外, dp[4][3] = dp[3][3] + dp[2][1], 这种情况下 dp[2][1] 应该取 1
5. 从 1 写到 5, 这个思路都 work, 不过仍是 WA 到死
update 2014年3月10日12:42:13
上面的状态转移方程是错误的.
在 (4) 中, 谈到了例外, 然而这个例外并不是唯一的. 当 n = 6 时, 求解 dp[6][5] = dp[5][5] + dp[4][3]
其中 dp[5][5] = 1, 而 dp[4][3] 是 2, 分别为 FFFM, MFFF.
但是, 少算了一个, FFMF, 因为已经确定了最后两位是 FF
dp[i][j] 表示在第 i 个位置放置男生(j = 0) 或女生(i = 0) 的方案数
那么 dp[i][0] = dp[i-1][0] + dp[i-1][1]
难点是求解 dp[i][1], dp[i][1] = dp[k][0] k = [0, i-2] 意思是第 i 个位置放女士, 那么第 i-1 个位置上也肯定是女生, 那么我们就枚举最后一个男生出现的位置
dp[k][0] 表示第 k 个位置上是男生的方案数, 同时也表示第 k 个位置上是男生且 k+1 -> i 位置上都是女生的方案数
可以用单调队列记录前 i-2 个位置上放男生的方案数, 这样, 时间复杂度下降到了 o(n)
代码
#include#include #include using namespace std;const int NO_DEFINE = 0x80808080;int solution[1001][3];int n;void init() { memset(solution, 0x80, sizeof(solution)); solution[1][0] = 1; solution[1][1] = 0; solution[1][2] = 1; solution[2][0] = 1; solution[2][1] = 1; solution[2][2] = 2;}int getSolution(int a, int b) { if(solution[a][b] != NO_DEFINE) return solution[a][b]; if(b == 0) return (solution[a][b] = (getSolution(a-1, 0)+ getSolution(a-1, 1))% 1000000007); else if(b == 1) { return (solution[a][b] = getSolution(a-1, 2))% 1000000007; } else { return (solution[a][b] = (getSolution(a-1, b)+getSolution(a-1, 0))% 1000000007); } }int main() { init(); while(scanf("%d", &n) != EOF) { int res = 0; for(int i = 0; i <= 1; i ++) { res = res + getSolution(n, i); res = (res >= 1000000007) ? res % 1000000007:res; } printf("%d\n", res); } return 0;}