HDU 1466 - Ji Suan Zhi Xian Jiao Dian Shu

Problem : List the number of intersecition for n lines in every situation.
Solution :
1) Using a number sequence to present a situation. Like '1 2' means there is a 3 lines situation s.t. there are two lines in parallel and 1 lines not parallel.

2) With observation, '3 2 1' has the same answer with '1 3 2'. Thus we only consider the situation that the sequence is in non-increasing order.

3) The non-increasing sequence with sum x and has element y (y!=1) must has one-to-one reflection to the non-increasing sequence with sum x-1 and has element y-1. When y=1, all the sequences with sum x-1 has one-to-one reflection with the sequence with sum x and has element y.(See the note for the proof)

4) Denote f[i][j][k] to indicate whether there exists a non-increasing sequence with the sum i, has element j and the number of intersection points k. Then f[i][j!=1][k]=f[i-1][j-1][k-i+j], f[i][1][k]=exists(f[i][j'][k-i+1]=1). j' is the any positive integer.

The total time is the number of status, O(N^4). The space can be reduced to O(N^3).