Zerojudge d653: VAC+ _ 社費問題

http://zerojudge.tw/ShowProblem?problemid=d653

這題要用到剪枝，一個情況是，在同一狀態下別選擇用過的數字，另一個情況則是，如果剩下的數字全選的話都還不夠，那就別再遞迴會下去了，因為根本不可能是答案。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int n, m;
int num[100], ans[100];

void DFS(int now, int index)
{
	if(now == m)
	{
		for(int i = 0; i < m; i ++)
			printf("%d ", ans[i]);
		printf("\n");

		return;
	}

	int last = -1;
	for(int i = index; i < n; i ++)
	{
		if(n - index < m - now) return;

		if(num[i] != last)
		{
			last = num[i];
			ans[now] = num[i];
			DFS(now + 1, i + 1);
		}
	}

}

int main()
{
	while(scanf("%d %d", &n, &m) == 2)
	{
		if(n == 0 && m == 0) break;

		for(int i = 0; i < n; i ++)
			scanf("%d", &num[i]);

		sort(num, num + n);

		DFS(0, 0);
	}

    return 0;
}

UVa 10400 – Game Show Math

題目來源:

http://uva.onlinejudge.org/index.phpoption=com_onlinejudge&Itemid=8&page=show_problem&problem=1341

題目翻譯:

http://luckycat.kshs.kh.edu.tw/homework/q10400.htm

題目大意:

給定n個正整數和一個目標數，問我們能否在這些正整數中，插入+ – * /使得運算式的結果等於目標數? 條件是這n個正整數順序不能改變，而計算的方式是由左到右，不必管運算的優先順序（就是不管先乘除後加減）。

解題心得:

原本以為是基本的DFS，後來才發現最差大概會執行 10^53 秒(因為n-1個運算子，所組成的運算式，有4^(n-1)種可能，最差的情況下每一種都要考慮)