刷題 Uva 10036 解答

我覺得這是一題很適合練習的dp題目

	#include <cstdio>
	#include <cstdlib>
	int n, k;
	int input[10000];
	int index;
	int map[10000][100];
	bool isDivisible;
	void dfs(int count, int total){
	if(count == n){
	if((total % k) == 0) isDivisible = true;
	return;
	}
	if(map[count][total] == index){
	return;
	}
	map[count][total] = index;
	dfs(count+1, (total + input[count] + k) % k);
	dfs(count+1, (total - input[count] + k) % k);
	}
	int main(){
	int m;
	scanf("%d", &m);
	for(int i = 0; i < m; i++){
	isDivisible = false;
	index++;
	scanf("%d%d", &n, &k);
	for(int j = 0; j < n; j++){
	scanf("%d", input + j);
	}
	dfs(0,0);
	if(isDivisible) puts("Divisible");
	else puts("Not divisible");
	}
	return 0;
	}

view raw 10036.cpp hosted with ❤ by GitHub