> 状态定义为：第一个棋子放在至少第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;
> }
> 
> 谁给个复杂度分析 :）

• Re:好像我写了深搜也没专门剪什么有时0ms有时16ms 。。交流交流。 不懂分析 (0) scuwf 2011-11-01 17:58:47
  • Re:好像我写了深搜也没专门剪什么有时0ms有时16ms 。。交流交流。 不懂分析 (38) scuwf 2011-11-01 17:59:34