携程笔试 5.7 研发方向1 专业笔试（二）讨论

#include <iostream>
#include <vector>
using namespace std;

int climb(int n) {
	if (n <= 0) return -1;

	vector<vector<int>> dp(n+1);
	for (int i = 0; i <= n; i++) dp[i].resize(2);

	dp[1][0] = dp[1][1] = 1;
	dp[2][0] = dp[2][1] = 2;
	dp[3][0] = 3;
	dp[3][1] = 4;
	
	for (int i = 4; i <= n; i++) {
		dp[i][0] = dp[i - 1][0] + dp[i - 2][0];
		dp[i][1] = dp[i - 1][1] + dp[i - 2][1] + dp[i - 3][0];
	}

	return dp[n][1];
}

int main() {
	int n;
	cin >> n;
	cout << climb(n) << endl;
	return 0;
}

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

const int MAXN = 30;
int G[MAXN][MAXN];
map<char, int> nameToIdx;
map<int, char> idxToName;
int N = 0;

vector<vector<int>> ans;
vector<int> path;
vector<bool> vis(MAXN);
int st, ed;

void dfs(int u) {
	vis[u] = true;
	path.push_back(u);
	if (u == ed) {
		ans.push_back(path);
	} else {
		for (int v = 0; v < N; v++) {
			if (G[u][v] && vis[v] == false) {
				dfs(v);
			}
		}

	}
	path.pop_back();
	vis[u] = false;
}

int convertNameToIndex(char name) {
	if (!('A' <= name && name <= 'Z')) {
		cout << "EMPTY" << endl;
		exit(0);
	}
	auto it = nameToIdx.find(name);
	if (it != nameToIdx.end()) {
		return it->second;
	} else {
		nameToIdx[name] = N;
		idxToName[N] = name;
		return N++;
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	string str;
	cin >> str;
	for (int i = 0; i < str.length(); i += 6) {
		char st = str[i + 1];
		char ed = str[i + 3];
		int u = convertNameToIndex(st);
		int v = convertNameToIndex(ed);
		G[u][v] = 1;
	}

	if (nameToIdx.count('A') == 0 || nameToIdx.count('B') == 0) {
		cout << "EMPTY" << endl;
		return 0;
	}

	st = nameToIdx['A'];
	ed = nameToIdx['B'];

	dfs(st);

	if (ans.size() == 0) {
		cout << "EMPTY" << endl;
		return 0;
	}

	sort(ans.begin(), ans.end(), [](const vector<int> &A, const vector<int> &B) {
		return A.size() < B.size();
		});

	cout << "[";
	for (int i = 0; i < ans.size(); i++) {
		if (i > 0) cout << ",";
		cout << "[";
		for (int j = 0; j < ans[i].size(); j++) {
			if (j > 0) cout << ",";
			cout << idxToName[ans[i][j]];
		}
		cout << "]";
	}
	cout << "]";
	cout << endl;
	return 0;
}

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int N, M;
vector<int> A;
vector<int> SUM;    // sum[i]表示数组前i个数字的和

vector<int> plan;

int cnt;

bool judge(vector<int> &plan) {
	set<int> S;
	int preCnt = 0;
	for (int x : plan) {
		int sum = SUM[preCnt + x] - SUM[preCnt];
		if (S.count(sum) > 0) return false;
		S.insert(sum);
		preCnt += x;
	}
	return true;
}

void dfs(int N, int M) {
	if (M == 0) {
		if (N == 0) {
			if (judge(plan)) {
				cnt++;
			}
		}
	} else {
		for (int i = 1; i <= N; i++) {
			plan.push_back(i);
			dfs(N - i, M - 1);
			plan.pop_back();
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	cin >> N;
	A.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	cin >> M;
	if (N < M) {
		cout << "0" << endl;
		return 0;
	}
	SUM.resize(N + 1);
	for (int i = 1; i <= N; i++) {
		SUM[i] = SUM[i - 1] + A[i - 1];
	}
	dfs(N, M);
	cout << cnt << endl;
	return 0;
}