結果

提出番号	1735
提出者	eiya
言語	C++
提出日時	2018-08-04 13:41:23
問題名	(70)アルゴリズムのお勉強
結果	CE
点数	0%

---

テストケース

ソースコード

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t N;

int32_t cost[16];
int32_t minus[16][16];
int32_t dp[1 << 16];


template<typename T, typename U>
std::enable_if_t<std::rank<T>::value == 0> fill_all(T& arr, const U& v) {
	arr = v;
}
template<typename ARR, typename U>
std::enable_if_t<std::rank<ARR>::value != 0> fill_all(ARR& arr, const U& v) {
	for (auto& i : arr) {
		fill_all(i, v);
	}
}

int32_t func(std::bitset<16> mask)
{
	if (mask == 0) { return 0; }
	if (dp[mask.to_ulong()] != -1) {
		return dp[mask.to_ulong()];
	}

	int32_t cost2[16] = {};
	for (int32_t i = 0; i < N; i++){
		cost2[i] = cost[i];
	}
	for (int32_t i = 0; i < N; i++)
	{
		if (!mask[i]) {
			for (int32_t j = 0; j < N; j++) {
				cost2[j] = std::max(0, cost2[j] - minus[i][j]);
			}
		}
	}

	int32_t res = 10001616;
	for (int32_t i = 0; i < N; i++)
	{
		if (mask[i]) {
			mask[i] = false;
			res = std::min(res, func(mask)+cost2[i]);
			mask[i] = true;
		}
	}
	return dp[mask.to_ulong()] = res;
}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	fill_all(dp, -1);

	in >> N;
	for (int32_t i = 0; i < N; i++)
	{
		in >> cost[i];
	}
	for (int32_t i = 0; i < N; i++)
		for (int32_t j = 0; j < N; j++)
	{
		in >> minus[i][j];
	}

	out << func((1 << N) - 1) << endl;;

	return 0;
}
#endif


#if 0
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;


class Trie
{
private:
	int8_t just = 0;
	uint16_t child_num = 0;
	std::unique_ptr<Trie> childlen['z'-'a'+1];
public:

	void insert(const char* str) {
		++child_num;
		if (*str == '\0') { ++just; return; }
		if (childlen[*str - 'a'] == nullptr) { childlen[*str - 'a'] = std::make_unique<Trie>(); }
		childlen[*str - 'a']->insert(str + 1);
	}

	int32_t count(const char* str)const {
		if (*str == '\0') { return just; }
		if (*str == '*') { return child_num; }
		if (*str == '?') {
			int32_t res = 0;
			for (auto& i : childlen)
			{
				if(i){ res += i->count(str + 1); }
			}
			return res;
		}

		if (childlen[*str - 'a']) {
			return childlen[*str - 'a']->count(str + 1);
		}
		else {
			return 0;
		}
	}
};

int32_t N, M;
std::string buf;
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N>>M;
	Trie trie;
	Trie trie_rev;
	buf.reserve(256);
	for (size_t i = 0; i < N; i++)
	{
		in >> buf;
		trie.insert(buf.c_str());
		std::reverse(buf.begin(), buf.end());
		trie_rev.insert(buf.c_str());
	}

	for (size_t i = 0; i < M; i++)
	{
		in >> buf;
		if (buf[0] == '*') {
			std::reverse(buf.begin(), buf.end());
			out << trie_rev.count(buf.c_str()) << endl;
		}
		else {
			out << trie.count(buf.c_str()) << endl;
		}
	}


	return 0;
}
#endif