首页 > ACM题库 > HDU-杭电 > hdu 3736 Choose The Soldiers待解决[解题报告]C++
2015
02-22

hdu 3736 Choose The Soldiers待解决[解题报告]C++

Choose The Soldiers

问题描述 :

There are N matrixs of soilders.
Now here comes an urgent task and you want to choose M of them to complete the task.
But if more than 2 selected soldiers are in the same row or column of the same matrix they will chat to each other and the efficiency will be too low.
Of course you want to avoid low efficiency.
How many ways can you choose them?

输入:

There are several test cases. The first line of the input is an integer T (0<T<=100) indicates the number of test cases.
The first line of each test case is a line of 2 positive integers N(0<N<=20) and M (0<M<=800).
Then N lines of 2 integers, m and n (0<m,n<=20) indicate the number of row and column of each matrix.

输出:

There are several test cases. The first line of the input is an integer T (0<T<=100) indicates the number of test cases.
The first line of each test case is a line of 2 positive integers N(0<N<=20) and M (0<M<=800).
Then N lines of 2 integers, m and n (0<m,n<=20) indicate the number of row and column of each matrix.

样例输入:

2
1 1
1 1
2 2
1 1
2 2

样例输出:

1
10


  1. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。