状态定义为：第一个棋子放在至少第r行，剩余k个棋子要放， f(r, k) 为可能的放法数
那么题目就是求 f(0, k) 

f(r, k)= 本行不放的情况 ＋ 本行放1个的情况 乘以 f(r+1, k-1) ， 

因为本行(第r行)放1个的话有多种方法，放哪里影响下一次放的位置，所以必须要记录棋盘状态和回溯。（不满足无后效性唉）

本行不放的情况＝f(r+1, k)+...+f(r+k-n, k) 

rm cm分别标记行和列是否可放

我的dfs如下
int dfs(int r, int k)
{
	int ret=0;
	if(k==0) return 1;
	for(int i=r; i<n-k+1; i++)
		for(int j=0; j<n; j++)
			if(cb[i][j]==1 && rm[i]==0 && cm[j]==0) // can place chess
			{
				rm[i]=1; cm[j]=1;
				ret+=dfs(r+1, k-1);
				rm[i]=0; cm[j]=0;
			}
	return ret;
}

谁给个复杂度分析 :）

• 我的程序是直接套用了回溯的通用代码,通用性强,但可能灵活性不够导致了效率问题.很郁闷.解数独的时候,也是因为效率不好导致TLE (0) gfedcba 2009-02-20 20:26:41
  • 刚看你的回复，再看看自己的代码，发现自己傻了。。。白白写多一重循环。改了 (331) userfriendly 2009-02-20 21:06:34
    • 你改后，AC的时间是不是每次都变成0MS？？ (0) gfedcba 2009-02-20 23:07:28
      • 没.... AC时间是跟RP挂钩的。 。。 我泪流满面 (0) userfriendly 2009-02-20 23:38:46
  • Re:我的程序是直接套用了回溯的通用代码,通用性强,但可能灵活性不够导致了效率问题.很郁闷.解数独的时候,也是因为效率不好导致TLE (15) blackerJT 2009-10-21 15:48:17
    • Re:我的程序是直接套用了回溯的通用代码,通用性强,但可能灵活性不够导致了效率问题.很郁闷.解数独的时候,也是因为效率不好导致TLE (19) 11111000208 2012-05-03 14:30:55
• Re:好像我写了深搜也没专门剪什么有时0ms有时16ms 。。交流交流。 不懂分析 (593) 1234556 2010-03-13 20:31:22
  • Re:好像我写了深搜也没专门剪什么有时0ms有时16ms 。。交流交流。 不懂分析 (0) scuwf 2011-11-01 17:58:47
    • Re:好像我写了深搜也没专门剪什么有时0ms有时16ms 。。交流交流。 不懂分析 (38) scuwf 2011-11-01 17:59:34