错解求卡(不知道为啥过了)
查看原帖
错解求卡(不知道为啥过了)
312811
kyEEcccccc楼主2023/5/16 22:49

暴力模拟,每次先往小的那一边递归,最优性剪枝。复杂度感觉不对,但是跑得飞快。

// Author: kyEEcccccc

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
using ULL = unsigned long long;

#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)

const int N = 100005;

int n, p, q, a[N], b[N];
LL ans = LLONG_MAX;

void solve(int l, int r, LL cur)
{
	if (cur >= ans) return;
	if (l > r) return MIN(ans, cur), void();
	int mid = l;
	F(i, l, r) if (a[i] < b[i]) swap(a[i], a[mid]), swap(b[i], b[mid++]);
	if (mid - l > r - mid + 1)
	{
		F(i, mid, r) swap(a[i], b[i]), b[i] -= a[i];
		F(i, mid, r) if (b[i] == 0) swap(a[i], a[r]), swap(b[i], b[r--]);
		solve(mid, r, cur + p + q);

		F(i, l, mid - 1) b[i] -= a[i];
		solve(l, mid - 1, cur + p);
	}
	else
	{
		F(i, l, mid - 1) b[i] -= a[i];
		solve(l, mid - 1, cur + p);

		F(i, mid, r) swap(a[i], b[i]), b[i] -= a[i];
		F(i, mid, r) if (b[i] == 0) swap(a[i], a[r]), swap(b[i], b[r--]);
		solve(mid, r, cur + p + q);
	}
}

signed main(void)
{
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(nullptr);

	cin >> n >> p >> q;
	F(i, 1, n) cin >> a[i] >> b[i];
	solve(1, n, 0);
	cout << ans << '\n';
	
	return 0;
}
2023/5/16 22:49
加载中...