Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

 D - Ordering T-shirts 

Background

Working in a boutique folding and putting in order T-shirts according to their sizes seems very easy. But is it really so simple?

The Problem

Given n objects of different sizes, how many different arrangements can be done using relationships "<" and "="?

For instance, with 2 objects, A and B, we have 3 possible arrangements:

A=B     A<B     B<A

With 3 objects, A, B and C, you must conclude that 13 different arrangements exist:

A=B=C     A=B<C     A<B=C     A<B<C     A<C<B     A=C<B     B<A=C     B<A<C     B<C<A     B=C<A     C<A=B     C<A<B     C<B<A

The Input

The first line of the input contains an integer, t, indicating the number of test cases. For each test case, one line appears, that contains a number n, 1<=n<=11, representing the number of objects.

The Output

For each test case, the output should contain a single line with the number representing the different arrangements you can do with n objects.

Sample Input

4
1
2
3
4

Sample Output

1
3
13
75

---

做法 : 窮舉 "<" "=" 的排列
再利用數學公式 n! / a!/b! ... 去做建表

#include <stdio.h>
#include <stdlib.h>
int step[12] = {}, ans[12] = {0, 1};
void Backtracking(int now) {
	if(now >= 12)
		return;
	if(now > 0) {
		int i, f = 1, c = now;
		int tmp = 2, count = 2;
		for(i = 2; i <= c+1; i++)
			f *= i;
		for(i = 0; i < c-1; i++) {
			if(step[i] == step[i+1] && step[i] == 2)
				count++, tmp *= count;
			else {
				if(step[i] == 2)
					f /= tmp, tmp = 2, count = 2;
			}
		}		
		if(step[i] == 2)
			f /= tmp, tmp = 2, count = 2;
		ans[c+1] += f;
	}
	step[now] = 0;
	Backtracking(now+1);
	step[now] = 2;
	Backtracking(now+1);
}
int main() {
	int t, n;
	Backtracking(0);
	scanf("%d", &t);
	while(t--) {
		scanf("%d", &n);
		printf("%d\n", ans[n]);
	}
    return 0;
}