地址 http://poj.org/problem?id=2431
题解
朴素想法就是dfs 经过该点的时候决定是否加油 中间加了一点剪枝 如果加油次数已经比已知最少的加油次数要大或者等于了 那么就剪枝
然而 还是TLE了
TLE代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue> using namespace std; vector<pair<int, int>> dis_fuel(); int n;
int L, P; int ret = ; void dfs(int idx,int currAddCount)
{
if (idx == n) {
ret = min(ret, currAddCount);
return;
} if (currAddCount >= ret) return; if (P + dis_fuel[idx].first >= L) {
//当前的油 可以到达 那么选择加油不加油 P += dis_fuel[idx].second;
dfs(idx+, currAddCount+); P -= dis_fuel[idx].second;
dfs(idx + , currAddCount);
} return;
} int solve()
{
cin >> n; for (int i = ; i < n; i++) {
cin >> dis_fuel[i].first >> dis_fuel[i].second;
}
cin >> L >> P; sort(dis_fuel.begin(), dis_fuel.begin() + n, greater<pair<int, int>>()); dfs(,); if (ret == ) ret = -;
return ret;
} int main()
{
cout << solve() << endl; return ;
}
TLE!!!
考虑下经过一个加油站就是增加了一个加油的机会 那么我们尝试不加油继续往前走 走到没有了 看看能经过多少加油站 然后从里面选择加油最多的那个机会 加油 再继续前行
这是很显然的贪心策略 既然要加油次数最少 那么在能加油的机会里贪心选择即可.未细加证明 但是AC了 说明思路是正确的
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue> using namespace std; vector<pair<int, int>> dis_fuel(); int n;
int L, P; int solve()
{
cin >> n; for (int i = ; i < n; i++) {
cin >> dis_fuel[i].first >> dis_fuel[i].second;
}
cin >> L >> P; int ret = ;
sort(dis_fuel.begin(), dis_fuel.begin() + n, greater<pair<int, int>>());
priority_queue<int, vector<int>,less<int>> que; for (int i = ; i < dis_fuel.size(); i++) {
if (dis_fuel[i].first + P >= L) {
que.push(dis_fuel[i].second);
}
else {
while (!que.empty() && dis_fuel[i].first + P < L) {
ret++;
P += que.top();
que.pop();
}
if (dis_fuel[i].first + P < L) return -;
que.push(dis_fuel[i].second);
}
} if (P < L) return -;
return ret;
} int main()
{
cout << solve() << endl; return ;
}