bitDP千本ノック

#include <iostream>
#include <vector>
//#include <limits.h>
#define INF (1LL << 30) //2,3回足してもオーバーフローせず、入力される可能性もないくらい大きな値を設定する事が大事

int main() {
    int N, M;
    std::cin >> N >> M;
    std::vector<int> A(M, 0), B(M, 0), takara(M,0); // takaraはi個目の鍵を使用して開けられる宝箱を格納する。（0：開けられない、1：開けられる）
    for (int m = 0; m < M; m++) {
        std::cin >> A[m] >> B[m];
        for (int b = 0; b < B[m]; b++) {
            int c;
            std::cin >> c;
            c--;// ビットシフトに使うため。(1は「000000000001 = 1 << 0」)
            takara[m] |= 1 << c;// シフトしてor演算
        }
    }

    //「1 ≦ N ≦ 12」より12ビットのbitDP
    std::vector<int> dp((1 << N), INF);
    dp[0] = 0;
    for (int i = 0; i < (1 << N); i++) {
        for (int takara_bako = 0; takara_bako < N; takara_bako++) {
            if (((i >> takara_bako) & 1) == 0) { //takara_bakoが空いていない
                for (int key = 0; key < M; key++) {
                    if (((takara[key] >> takara_bako) & 1) == 1) { //keyでtakara_bakoを開けられる
                        int v = (i | takara[key]); //「現在の状態iからkeyを買うと開けられるようになる宝箱の状態」の値を更新する
                        dp[v] = std::min(dp[v], dp[i] + A[key]);
                    }
                }
            }
        }
    }
    int ans = dp[(1 << N) - 1];
    std::cout << (ans == INF ? -1 : ans) << std::endl;
}

#include <iostream>
#include <vector>
#define INF (1LL << 30)

struct City {
	int X, Y, Z;
};

int distance(City from, City to) {
	return abs(to.X - from.X) + abs(to.Y - from.Y) + std::max(0, (from.Z - to.Z));
}

int main() {
	int N;
	std::cin >> N;
	std::vector<City> Cities(N);
	for (int n = 0; n < N; n++) std::cin >> Cities[n].X >> Cities[n].Y >> Cities[n].Z;

	std::vector<std::vector<int>> dp((1 << N), std::vector<int>(N, INF));
	dp[0][0] = 0;
	for (int visited_cities = 0; visited_cities < (1 << N); visited_cities++) {
		for (int last_city = 0; last_city < N; last_city++) {
			for (int to_visit = 0; to_visit < N; to_visit++) {
				if ((((visited_cities >> to_visit) & 1) == 1)&&(to_visit != 0)) {
					// 訪問済みの都市に訪れようとしていない、かつ、訪問しようとしている都市がホームタウンでない（ホームタウンへの再訪問は帰宅のために認められる）
					continue;
				}
				else {
					int new_visited_cities = (visited_cities | 1 << to_visit);
					dp[new_visited_cities][to_visit] = std::min(dp[new_visited_cities][to_visit], dp[visited_cities][last_city] + distance(Cities[last_city], Cities[to_visit]));
				}
			}
		}
	}

	std::cout << dp[(1 << N) - 1][0] << std::endl;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>

int main() {
	/*
	* 問題文の読み違えに注意。
	* 「1≤i≤M を満たす全ての整数 i について～」⇒　M個の条件をすべて満たせ
	*/
	const int N_MAX = 18;
	int N, M;
	std::cin >> N >> M;
	std::vector<int> X(M, 0), Y(M, 0), Z(M, 0);
	for (int m = 0; m < M; m++) std::cin >> X[m] >> Y[m] >> Z[m];

	/*
	* 以下をやるとTLEしそうなので他の方法を考える
	std::vector<int> A(N, 0);
	for (int n = 1; n <= N; n++) A[n - 1] = n;
	do {

	} while (std::next_permutation(A.begin(), A.end()));
	*/

	std::vector<long long> dp((1 << N), 0);
	dp[0] = 1; //「開始は00000だからそれを１通りとしておく」らしい。ちょっとまだ納得いかない。なんで？
	for (int selected_nums = 0; selected_nums < (1 << N); selected_nums++) {
		//selected_nums内で1が立っているビット（＝選択されている数）の個数を計算しておく
		int cnt = 0;
		std::bitset<N_MAX> bs(selected_nums);
		for (int i = 0; i < N; i++) if (bs[i] == 1) cnt++;//「if (((selected_nums >> i) & 1) == 1)」でも可。処理時間はあまり変わらなかった。
		
		for (int next_num = 0; next_num < N; next_num++) {
			if (((selected_nums >> next_num) & 1) == 0) { //selected_numsにnext_numが含まれていないか判定
				bool is_ok = true;
				for (int m = 0; m < M; m++) {
					if (X[m] == cnt) { //X[i]=cntのものだけ条件を確認すればいい。それ以前のものはdpの更新的には条件が満たされていることが確約されているので確認しなくてもいい
						int tmp_cnt = 0;
						for (int i = 0; i < Y[m]; i++) { //「Yi以下の個数」＝「右から数えて 3 番目の数字までの 1 の数」
							if (((selected_nums >> i) & 1) == 1) tmp_cnt++; //「if (bs[i] == 1)」でもいいがstd::bitset使うよりシフト演算の方が早い
						}
						if (Z[m] < tmp_cnt) is_ok = false; //Zの判定
					}
				}
				if (is_ok == true) {
					int v = (selected_nums | (1 << next_num));
					dp[v] += dp[selected_nums]; //動的計画法の階段の問題と似た考え方。遷移後の場合の数＝遷移できる場合の数の総和。
				}
			}
		}
	}

	std::cout << dp[(1 << N) - 1] << std::endl; //N個の数を並び替えてできる数列（のうち、条件を満たすもの）の数を考えるのでdp[(1 << N) - 1]に本問題の答えが入る。
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF (1LL << 30)

struct TreeNode {
	std::vector<int> Children;
	bool is_checked = false;
};

int main() {
	int N, M, K, a, b, c;
	std::cin >> N >> M;
	std::vector<TreeNode> Tree(N);
	for (int m = 0; m < M; m++) {
		std::cin >> a >> b;
		a--; b--;
		Tree[a].Children.push_back(b);
		Tree[b].Children.push_back(a);
	}
	std::cin >> K;
	std::vector<int> C(K, 0);
	for (int k = 0; k < K; k++) {
		std::cin >> c;
		c--;
		C[k] = c;
	}

	//BFSで目的の魔法石同士の距離を計算する。
	auto bfs = [&](int i){
		for (int n = 0; n < N; n++) Tree[n].is_checked = false;

		std::vector<int> cost(N, INF);
		cost[i] = 0;
		std::queue<int> q;
		q.push(i);
		while (0 < q.size()) {
			int x = q.front();
			q.pop();
			for (int y : Tree[x].Children) {
				if (Tree[y].is_checked == false) {
					Tree[y].is_checked = true;
					cost[y] = std::min(cost[y], cost[x] + 1);
					q.push(y);
				}
			}
		}
		// returnするcostをCに含まれているものだけに絞る
		for (int k = 0; k < K; k++) cost[k] = cost[C[k]];
		cost.resize(K);
		return cost;
	};
	// distance[i][j]：C[i]からC[k]までの最短距離
	std::vector<std::vector<int>> distance(K, std::vector<int>(K, INF));
	for (int k = 0; k < K; k++) distance[k] = bfs(C[k]);

	//ここまでくれば普通の巡回セールスマン問題と同じ感覚でbitDP
	std::vector<std::vector<int>> dp((1 << K), std::vector<int>(K, INF));
	for (int k = 0; k < K; k++) dp[(1 << k)][k] = 1; //最初は好きに1つ置けるため
	for (int selected = 0; selected < (1 << K); selected++) {
		for (int last = 0; last < K; last++) {
			if (((selected & (1 << last)) == 0) && (selected != 0)) {
				continue;
			}
			for (int next = 0; next < K; next++) {
				if ((((selected >> next) & 1) == 0)&&(distance[last][next] != INF)) {
					int v = (selected | (1 << next));
					dp[v][next] = std::min(dp[v][next], dp[selected][last] + distance[last][next]);
				}
			}
		}
	}
	//最後にどれを追加したかは関係ないので「(1<<K)-1」行目のdpテーブルの最小値を回答する。
	int ret = * min_element(dp[(1 << K)-1].begin(), dp[(1 << K)-1].end());
	std::cout << (ret == INF ? -1 : ret) << std::endl;
}

#include <iostream>
#include <vector>

#define INF (1LL << 30)

int main() {
	int N;
	std::cin >> N;
	std::vector<std::vector<int>> D(N, std::vector<int>(N, 0));
	for (int i = 0; i < N; i++) {
		for (int j = i; j < N; j++) {
			if (i == j) continue;
			std::cin >> D[i][j];
			D[j][i] = D[i][j];
		}
	}

	std::vector<long long> dp((1 << N), 0);
	for (int selected = 0; selected < (1 << N); selected++) {
		for (int next_s = 0; next_s < N; next_s++) {
			if (((selected >> next_s) & 1) == 1) continue;
			for (int next_e = 0; next_e < N; next_e++) {
				if (((selected >> next_e) & 1) == 0) {
					if (next_s != next_e) {
						int v = (selected | (1 << next_s) | (1 << next_e));
						dp[v] = std::max(dp[v], dp[selected] + D[next_s][next_e]);
						int a = 0;
					}
				}
			}
		}
	}
	if ((N % 2) == 0) {
		std::cout << dp[(1 << N) - 1] << std::endl;
	}
	else {
		long long ret = 0;
		for (int n = 0; n < N; n++) ret = std::max(ret, dp[((1 << N) - 1) ^ (1 << n)]);
		std::cout << ret << std::endl;
	}
}

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

#define INF (1LL << 30)

int dx[3] = { -1, 0, 1 };
int dy[3] = { -1, 0, 1 };

int main() {
	int H, W, T;
	std::cin >> H >> W >> T;
	std::vector<std::vector<char>> Grid(H, std::vector<char>(W, ' '));
	std::pair<int, int> Start;
	std::pair<int, int> Goal;
	std::vector<std::pair<int, int>> Okashi;
	for (int h = 0; h < H; h++) {
		for (int w = 0; w < W; w++) {
			char c;
			std::cin >> c;
			Grid[h][w] = c;
			if (c == 'S') Start = { h, w };
			if (c == 'G') Goal = { h, w };
			if (c == 'o') Okashi.push_back({ h,w });
		}
	}

	auto bfs = [&](std::pair<int, int> from, std::pair<int, int> to) {
		std::vector<std::vector<long long>> dist(H, std::vector<long long>(W, -1));
		std::queue<std::pair<int, int>> q;
		q.push(from);
		dist[from.first][from.second] = 0;

		while (0 < q.size()) {
			std::pair<int, int> tmp = q.front();
			q.pop();
			for (auto x : dx) {
				for (auto y : dy) {
					if ((x == 0) && (y == 0)) continue;
					if ((x != 0) && (y != 0)) continue;
					int tmp_x = (tmp.first + x);
					int tmp_y = (tmp.second + y);
					if ((tmp_x < 0) || (H <= tmp_x)) continue;
					if ((tmp_y < 0) || (W <= tmp_y)) continue;
					if (Grid[tmp_x][tmp_y] == '#') continue;
					if (dist[tmp_x][tmp_y] != -1) continue;
					
					dist[tmp_x][tmp_y] = (dist[tmp.first][tmp.second] + 1);
					if ((tmp_x == to.first) && (tmp_y == to.second)) return dist[tmp_x][tmp_y];
					q.push({ tmp_x, tmp_y });
				}
			}
		}
		return INF; //お菓子同士がたどりつけないパターンがあることに注意！　これが抜けていたせいでREを連発した。。
	};

	// BFSとbitDP
	/*アイデア１
	* ①スタートからゴールまでの最短経路と必要な移動回数を求める
	* ②各お菓子間を移動するのに必要な移動回数を求める
	* ③スタートからゴールまでの最短経路を通った時に出来る余裕の中で拾えるお菓子の最大値を求める
	*/
	/*アイデア２
	* ①スタート～お菓子１～ゴールの最短経路と必要な移動回数を求める
	* ②スタート～お菓子２～ゴール、スタート～お菓子１～お菓子２～ゴール、・・・の最短経路と必要な移動回数を求める
	* ③必要な移動回数がT以下、かつ拾えたお菓子（立っているbitの数）が最大の経路が答え
	*/
	/*アイデア３
	* ①各お菓子間を移動するのに必要な移動回数を求める
	* ②あるお菓子～スタート間と、あるお菓子～ゴール間を移動するのに必要な移動回数を求める。
	* ③スタート～お菓子２～ゴール、スタート～お菓子１～お菓子２～ゴール、・・・の最短経路と必要な移動回数を求める
	* 　※最後に拾ったお菓子～ゴール間を移動するのに必要な移動回数を除算し、最後に拾ったお菓子～次に拾うお菓子間を移動するのに必要な移動回数と次に拾うお菓子～ゴール間を移動するのに必要な移動回数を足す。
	* ④必要な移動回数がT以下、かつ拾えたお菓子（立っているbitの数）が最大の経路が答え
	*/

	std::vector<std::vector<long long>> distance(Okashi.size(), std::vector<long long>(Okashi.size(), INF));
	for (int row = 0; row < Okashi.size(); row++) {
		for (int col = 0; col < Okashi.size(); col++) {
			if ((distance[row][col] == INF)&&(row != col)) {
				distance[row][col] = bfs(Okashi[row], Okashi[col]);
				distance[col][row] = distance[row][col];
			}
		}
	}

	int move_count_strat_goal = bfs(Start, Goal);
	if (T < move_count_strat_goal) {
		std::cout << -1 << std::endl;
		return 0;
	}
	else if (Okashi.size() <= 0) {
		std::cout << Okashi.size() << std::endl;
		return 0;
	}
	else {
		std::vector<std::vector<long long>> dp((1 << Okashi.size()), std::vector<long long>(Okashi.size(), INF));
		dp[0][0] = move_count_strat_goal;
		for (int i = 0; i < Okashi.size(); i++) dp[(1 << i)][i] = bfs(Start, Okashi[i]) + bfs(Okashi[i], Goal);
		std::vector<int> OkashiToGoals(Okashi.size(), 0);
		for (int i = 0; i < Okashi.size(); i++) OkashiToGoals[i] = bfs(Okashi[i], Goal);

		for (int got_okashis = 0; got_okashis < (1 << Okashi.size()); got_okashis++) {
			for (int last = 0; last < Okashi.size(); last++) {
				if (((got_okashis >> last) & 1) == 0) continue;
				for (int next = 0; next < Okashi.size(); next++) {
					if (((got_okashis >> next) & 1) == 1) continue;
					int v = (got_okashis | (1 << next));
					//int dist_last_next = bfs(Okashi[last], Okashi[next]);
					//int dist_next_goal = bfs(Okashi[next], Goal);
					//int dist_last_goal = bfs(Okashi[last], Goal);
					//dp[v][next] = std::min(dp[v][next], dp[got_okashis][last] + dist_last_next + dist_next_goal - dist_last_goal);
					dp[v][next] = std::min(dp[v][next], dp[got_okashis][last] + distance[last][next] + OkashiToGoals[next] - OkashiToGoals[last]);
				}
			}
		}

		int ret = 0;
		for (int i = 0; i < (1 << Okashi.size()); i++) {
			int min_dist = * min_element(dp[i].begin(), dp[i].end());
			if (min_dist <= T) {
				int tmp_ret = 0;
				for (int b = 0; b < Okashi.size(); b++) if (((i >> b) & 1) == 1) tmp_ret++;
				ret = std::max(ret, tmp_ret);
			}
		}
		std::cout << ret << std::endl;
	}
}

#include <iostream>
#include <vector>
#include <algorithm>

#define INF (1LL<<30)
#define INF_ -(1LL<<30)

struct Color {
	char Name;
	int Score;
};

int main() {
	int n, m, Y, Z;
	std::cin >> n >> m >> Y >> Z;
	std::vector<Color> Colors(m);
	for (int i = 0; i < m; i++) std::cin >> Colors[i].Name >> Colors[i].Score;
	std::string order;
	std::cin >> order;

	std::vector<std::vector<std::vector<int>>> dp(n+1, std::vector<std::vector<int>>((1 << m), std::vector<int>(m, INF_)));
	dp[0][0][0] = 0;//初期スコアは0のため
	for (int cnt = 0; cnt < n; cnt++) {
		for (int used = 0; used < (1 << m); used++) {
			for (int last = 0; last < m; last++) {
				if ((((used >> last) & 1) == 0)&&(used != 0)) continue; //積んで無い状態からの積み上げを許可する
				if (dp[cnt][used][last] == INF_) continue; //一度も更新されてないdp状態からは処理をスタートしない

				int next = 0;
				for (int i = 0; i < m; i++) if (Colors[i].Name == order[cnt]) next = i;

				//積み上げないときの処理
				dp[cnt + 1][used][last] = std::max(dp[cnt + 1][used][last], dp[cnt][used][last]);

				//積み上げるときの処理
				int tmp_score = 0;
				if ((last == next) && (cnt != 0) && (used != 0)) {
					tmp_score += Y; // 初めの一回はボーナス加算しない！！
				}
				tmp_score += Colors[next].Score;
				int v = (used | (1 << next));
				dp[cnt + 1][v][next] = std::max(dp[cnt + 1][v][next], dp[cnt][used][last] + tmp_score);
			}
		}
	}

	for (int last = 0; last < m; last++) {
		if (dp[n][(1 << m) - 1][last] != 0) dp[n][(1 << m) - 1][last] += Z;
	}
	int ret = INF_;
	for (int used = 0; used < (1 << m); used++) {
		ret = std::max(ret, *max_element(dp[n][used].begin(), dp[n][used].end()));
		/*for (int last = 0; last < m; last++) {
			ret = std::max(ret, dp[n][used][last]);
		}*/
	}

	//int ret = * max_element(dp[n][(1 << m) - 1].begin(), dp[n][(1 << m) - 1].end());
	std::cout << ret << std::endl;
}