这道题用01背包真的过不了吗
查看原帖
这道题用01背包真的过不了吗
351392
a1029楼主2021/9/23 20:13
#include <bits/stdc++.h>
using namespace std;

int n, k;
string s[2005], ans = "}"; 

inline void dfs(register int dep, register string path) {
	if (path >= ans) return;
	if (dep > n) {
		if (path.size() == k && path < ans) ans = path;
		return;
	}
	if (path.size() == k) {
		if (path < ans) ans = path;
		return;
	}
	dfs(dep + 1, path + s[dep]);
	dfs(dep + 1, path);
} 

int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> k;
	for (register int i = 1; i <= n; i++)
		cin >> s[i];
	dfs(1, "");
	cout << ans << endl;
	return 0;
}

2021/9/23 20:13
加载中...