【LOJ3158】「NOI2019」序列

【題目連結】

點選打開連結

【思路要點】

筆者本題的做法是基于對決策點進行打表得到的，并不能給出嚴格的證明。但确實得到了一個與标準解法，或是模拟費用流解法完全不同的做法。

考慮一個 O ( N 3 ) O(N^3) O(N3) 的動态規劃，将數組按照 a i a_i ai 排序，那麼一旦确定了 L L L 對都選的位置，剩餘的 K − L K-L K−L 個選擇 a i a_i ai 的位置一定是一個字首。

是以，我們可以隻在狀态中計入考慮了的位置數，決策都選的位置數，決策選 b i b_i bi 位置數，則顯然有 O ( 1 ) O(1) O(1) 轉移。

此部分做法可以參見下方代碼 185 185 185 行起的内容。

将最優的決策點打表，可以發現所有 “都選” 的決策都排在 “選 b i b_i bi” 的決策之前，是以，若枚舉一個分界點，我們可以将問題分成兩個子問題進行求解。

上述動态規劃的時間複雜度就變為了 O ( N 2 ) O(N^2) O(N2) ，而處理 “選 b i b_i bi” 的決策隻需要用一個堆即可做到 O ( N L o g N ) O(NLogN) O(NLogN) 。

此部分做法可以參見下方代碼 123 123 123 行起的内容。

上述算法的時間複雜度瓶頸在于動态規劃，考慮再将 “都選” 的決策點集合打表，可以發現長度為 i i i 的字首對應的最優決策點的集合與長度為 i + 1 i+1 i+1 的字首對應的最優決策點的集合至多相差一個元素。

是以，隻要用堆維護決策點集合，貪心地進行替換即可。

時間複雜度 O ( N L o g N ) O(NLogN) O(NLogN) 。

【代碼】

// O(N Log N)
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;
	for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	x *= f;
}
int n, m, l;
bool sel[MAXN];
ll dp[MAXN], sa[MAXN];
pair <int, int> a[MAXN];
priority_queue <int> q;
struct Heap {
	priority_queue <pair <ll, int> > Heap, Delt;
	void clear() {
		while (!Heap.empty()) Heap.pop();
		while (!Delt.empty()) Delt.pop();
	}
	void ins(pair <ll, int> x) {
		Heap.push(x);
	}
	int size() {
		return Heap.size() - Delt.size();
	}
	void del(pair <ll, int> x) {
		Delt.push(x);
	}
	pair <ll, int> query() {
		while (!Heap.empty() && !Delt.empty() && Heap.top() == Delt.top()) {
			Heap.pop();
			Delt.pop();
		}
		if (Heap.empty()) return make_pair(-2000000000, 0);
		else return Heap.top();
	}
} Heap, Heaq;
int main() {
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
	int T; read(T);
	while (T--) {
		read(n), read(m), read(l);
		for (int i = 1; i <= n; i++)
			read(a[i].first);
		for (int i = 1; i <= n; i++)
			read(a[i].second);
		sort(a + 1, a + n + 1);
		reverse(a + 1, a + n + 1);
		memset(dp, -1, sizeof(dp));
		for (int i = 1; i <= n; i++)
			sa[i] = sa[i - 1] + a[i].first;
		Heap.clear();
		ll cur = 0;
		for (int i = 1; i <= m; i++) {
			cur += a[i].second;
			Heap.ins(make_pair(-a[i].second, i));
			if (Heap.size() > l) {
				cur += Heap.query().first;
				Heap.del(Heap.query());
			}
			if (i >= l) dp[i] = sa[i] + cur;
		}
		memset(sel, false, sizeof(sel));
		for (int i = 1; i <= l; i++) {
			sel[Heap.query().second] = true;
			Heap.del(Heap.query());
		}
		Heap.clear(), Heaq.clear();
		int point = 0;
		for (int i = 1; i <= m; i++)
			if (!sel[i]) point = i;
		for (int i = 1; i <= m; i++)
			if (sel[i]) {
				if (i > point) Heap.ins(make_pair(-a[i].first - a[i].second, i));
				else Heaq.ins(make_pair(-a[i].second, i));
			}
		for (int i = m + 1; i <= n; i++) {
			ll inc = a[i].first + a[i].second;
			dp[i] = dp[i - 1];
			if (Heap.query().first > Heaq.query().first - a[point].first && Heap.query().first + inc > 0) {
				dp[i] += Heap.query().first + inc;
				Heap.del(Heap.query());
				Heap.ins(make_pair(-inc, i));
			} else if (point != 0 && Heap.query().first <= Heaq.query().first - a[point].first && Heaq.query().first - a[point].first + inc > 0) {
				dp[i] += Heaq.query().first - a[point].first + inc; point--;
				sel[i] = true, sel[Heaq.query().second] = false;
				Heaq.del(Heaq.query());
				while (point > 0 && sel[point]) {
					Heap.ins(make_pair(-a[point].first - a[point].second, point));
					Heaq.del(make_pair(-a[point].second, point));
					point--;
				}
				Heap.ins(make_pair(-inc, i));
			}
		}
		while (!q.empty()) q.pop();
		ll ans = 0, now = 0;
		if (m == l) ans = dp[n];
		for (int i = n; i >= 1; i--) {
			now += a[i].second;
			q.push(-a[i].second);
			if (q.size() > m - l) {
				now += q.top();
				q.pop();
			}
			if (q.size() == m - l) {
				ll add = 0;
				if (i - 1 < m) add = sa[m] - sa[i - 1];
				chkmax(ans, dp[i - 1] + now + add);
			}
		}
		cout << ans << endl;
	}
	return 0;
}
// O(N ^ 2)
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 5;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;
	for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	x *= f;
}
int n, m, l;
ll dp[MAXN][MAXN], sa[MAXN];
pair <int, int> a[MAXN];
priority_queue <int> q;
int main() {
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
	int T; read(T);
	while (T--) {
		read(n), read(m), read(l);
		for (int i = 1; i <= n; i++)
			read(a[i].first);
		for (int i = 1; i <= n; i++)
			read(a[i].second);
		sort(a + 1, a + n + 1);
		reverse(a + 1, a + n + 1);
		memset(dp, -1, sizeof(dp));
		dp[0][0] = 0;
		for (int i = 0; i <= n - 1; i++)
		for (int j = 0; j <= l; j++) {
			ll tmp = dp[i][j];
			if (tmp != -1) {
				if (j < l) chkmax(dp[i + 1][j + 1], tmp + a[i + 1].first + a[i + 1].second);
				int add = (i + 1 - j <= m - l) ? (a[i + 1].first) : 0;
				chkmax(dp[i + 1][j], tmp + add);
			}
		}
		while (!q.empty()) q.pop();
		ll ans = 0, now = 0;
		if (m == l) ans = dp[n][m];
		for (int i = 1; i <= n; i++)
			sa[i] = sa[i - 1] + a[i].first;
		for (int i = n; i >= 1; i--) {
			now += a[i].second;
			q.push(-a[i].second);
			if (q.size() > m - l) {
				now += q.top();
				q.pop();
			}
			if (q.size() == m - l) {
				ll add = 0;
				if (i - 1 < m) add = sa[m] - sa[i - 1];
				chkmax(ans, dp[i - 1][l] + now + add);
			}
		}
		cout << ans << endl;
	}
	return 0;
}
// O(N ^ 3)
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 155;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;
	for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	x *= f;
}
int n, m, l;
ll dp[MAXN][MAXN][MAXN];
pair <int, int> a[MAXN];
int main() {
	freopen("sequence.in", "r", stdin);
	freopen("force.out", "w", stdout);
	int T; read(T);
	while (T--) {
		read(n), read(m), read(l);
		for (int i = 1; i <= n; i++)
			read(a[i].first);
		for (int i = 1; i <= n; i++)
			read(a[i].second);
		sort(a + 1, a + n + 1);
		reverse(a + 1, a + n + 1);
		memset(dp, -1, sizeof(dp));
		dp[0][0][0] = 0;
		for (int i = 0; i <= n - 1; i++)
		for (int j = 0; j <= l; j++)
		for (int k = 0; k <= m - l; k++) {
			ll tmp = dp[i][j][k];
			if (tmp != -1) {
				if (j < l) chkmax(dp[i + 1][j + 1][k], tmp + a[i + 1].first + a[i + 1].second);
				int add = (i + 1 - j <= m - l) ? (a[i + 1].first) : 0;
				if (k < m - l) chkmax(dp[i + 1][j][k + 1], tmp + a[i + 1].second + add);
				chkmax(dp[i + 1][j][k], tmp + add);
			}
		}
		cout << dp[n][l][m - l] << endl;
	}
	return 0;
}

【LOJ3158】「NOI2019」序列

繼續閱讀

【CodeForces553E】Kyoya and Train

【CodeForces1202F】You Are Given Some Letters...

【BZOJ3534】【SDOI2014】重建

【LOJ2553】「CTSC2018」暴力寫挂

【LOJ6403】「ICPC World Finals 2018」趕飛機

【LOJ6406】「ICPC World Finals 2018」綠寶石之島

【校内訓練2019-03-22】禮物

【BZOJ3277】串

【BZOJ5205】【LOJ6301】「CodePlus 2018 3 月賽」白金元首與莫斯科

bzoj 2151 種樹貪心+堆

【LOJ2950】「NOIP2018」鋪設道路

【BZOJ4755】【JSOI2016】扭動的回文串

【BZOJ1337】最小圓覆寫

【BZOJ2002】【HNOI2010】Bounce 彈飛綿羊

【AtCoder】AtCoder Regular Contest 092 題解

【BZOJ2733】【HNOI2012】永無鄉