1182部分数列の和

9639 ワード
白駿 テキストリンク

Nの最高値は20なので、逆追跡で近づくことができます.
解は解ですが、もっと簡単な解があります.
整数の個数が5の場合
部分数列は1個~5個からなる数列であるべきである.
だから部分的に列を数える.
川が形成されると
2つの数が構成されているとき...
除算して結果値を求めた.

マイコード

#include <iostream>
#include <vector>

using namespace std;

int n, s;
int answer = 0;
vector<int> sequence(30);

void back(int index, int num, int curSum, int total)
{
	if (num == total)
	{
		if (curSum == s)
			answer++;

		return;
	}

	for (int i = index; i < n; i++)
		back(i + 1, num + 1, curSum + sequence[i], total);
	

}
int main()
{
	cin >> n >> s;

	for (int i = 0; i < n; i++)
		cin >> sequence[i];

	for (int i = 1; i <= n; i++)
		back(0, 0, 0, i);

	cout << answer;
}
ただしfor文では、構成部分の数列の個数に基づいて
値切る必要はありません.
いずれの場合も部分数列の数を形成する.
各要素を選択して求めるかどうかしか考えられません.

単純コード

#include <iostream>
#include <vector>

using namespace std;

int n, s, answer = 0;
vector<int> sequence(30, 0);

void back(int num, int sum)
{
	if (num == n)
		return;

	sum = sum + sequence[num];

	if (sum == s)
		answer++;

	back(num + 1, sum);
	back(num + 1, sum - sequence[num]);
}

int main()
{
	cin >> n >> s;

	for (int i = 0; i < n; i++)
		cin >> sequence[i];

	back(0, 0);

	cout << answer;
	
}
JAvaマルチスレッド(二)--複数のスレッドが共有オブジェクトとデータにアクセスする方法
第13部:プロトコルとインクリメンタルゲートウェイモード(復習)