第三题直接暴力DFS不知道能不能过?
#include<iostream>
#include<vector>
using namespace std;
void dfs(int &maxScore, int aScore, int bScore, int curScore, vector<pair<int, int>> &score, int layer)
{
if (aScore>0 && bScore>0 && aScore == bScore)
{
maxScore = curScore < maxScore? maxScore : curScore;
return;
}
if (layer >= score.size())
return;
dfs(maxScore, aScore + score[layer].first, bScore, curScore + score[layer].second, score, layer + 1);
dfs(maxScore, aScore, bScore + score[layer].first, curScore + score[layer].second, score, layer + 1);
dfs(maxScore, aScore, bScore, curScore, score, layer + 1);
}
int main()
{
int n;
cin >> n;
int x, y;
vector<pair<int, int>> score;
for (int i = 0; i < n; i++)
{
cin >> x >> y;
score.push_back({ x, y });
}
int res;
dfs(res, 0, 0, 0, score, 0);
cout << res << endl;
system("pause");
return 0;
}