首页 > ACM题库 > HDU-杭电 > hdu 2431 Counting Problem-递推-[解题报告]C++
2014
01-26

hdu 2431 Counting Problem-递推-[解题报告]C++

Counting Problem

问题描述 :

      Yes. Counting problem comes again.
      Given a chess board of N*N (N<=500), how many ways are there to put N queens on it so that no queen can attack another?
      Luckily this is not the problem you should solve in this contest. Instead, we have a much easier one here.
      Given a chess board of N*N (N<=500), how many ways are there to put 2*N queens on it so that there are exactly two queens in each row and each column?
      To make it even easier, we will consider one way to be the same with another if it can be transformed to the other one by swapping rows and swapping columns.

输入:

      The first line of the input is an integer T indicating the number of cases.
      Line 2..T+1 will contain an positive integer N (N <=500) each.

输出:

      The first line of the input is an integer T indicating the number of cases.
      Line 2..T+1 will contain an positive integer N (N <=500) each.

样例输入:

3
2
5
4

样例输出:

1
2
2

题意: 问 n * n 的格子里面放 2*n个皇后的放法数,满足每行每列的皇后数都是2。

分析: 解法可以由前面的递推到后面,知道 2 * 2 的图有一种情况后,可知大于 2 * 2 的图都可以预留 2 * 2 的空间,对预留之后的 (N – 2) * (N – 2) 进行处理,以此类推

/***************************************
* File Name:2431.cpp
* Created Time:2013年12月14日 10:56:21
***************************************/
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 501;
const int mod = 1000007;
int f[maxn];

void init(){
    f[0] = 1;
    for (int i=2; i<maxn; i++){
        for (int j=i; j<maxn; j++){
            f[j] += f[j-i];
            if (f[j] >= mod){
                f[j] -= mod;
            }    
        }
    }
}
int main(){
    int T;
    int n;
    init();
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        printf("%d\n",f[n]);
    }
    return 0;
}

 

解题转自:http://www.cnblogs.com/sky0917/archive/2013/12/14/3474148.html


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法