把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

POJ3245 Sequence Partitioning
题目大意：给n对（<=5e4）数对(ai,bi)，要求将其分组，使得每组中的bi最小值要大于之后的组中ai的最大值，在这样的分组中，要保证每一组中的ai最大值之和不超过lmt（1e9），求满足条件的划分中使得每组中bi之和的最大值最小的分法，输出最小值。

解：

一开始是一个比较绕的讲解，很容易想到先将所有可以划分的位置都记录下来，并且记录这些划分组的ai最大值以及bi之和，接下来问题就转化为将这些划分出的区间进行合并，使得a[i]最大值之和小于lmt，bi之和最大，由于双限制，必须将其中一道限制转掉，于是选择去二分答案，判断在lmt限制下能否达到这个答案。
接下来就是要求在满足使得答案能够达到二分的mid值以内的情况下能否限制在lmt之内，由于区间段数太多，可以选择用贪心+dp解决，也就是说ai最大值之和必须尽可能小，根据区间合并的常规状态转移，可以得到dp[i]=dp[k]+max(a[i+1],…,a[k])，（在保证sumB[k]-sumB[i]<=mid的情况下），但是N2是不能去碰的，于是只能想到用一些方式进行优化。
观察状态转移，可以发现dp[i]是永远递增的，这一点非常关键：首先这说明了在我确定了后面的max要选哪个值的时候，我的k值可以尽可能小；其次这说明了最大值和次大值之间可以进行状态转移，因此选用单调队列的方法，但是发现由于参数比较多（需要同时记录区间最大值和dp的区间最小值），所以没有什么特别好用的创建单调队列的方法。
于是学习了使用multiset对单调队列进行映射，单调队列来维护最大值，multiset来维护区间最小值，转移的时候永远是最大值和次大值进行转移，也就是说当次大值出现在位置k2的时候，如果最大值的位置是k1，那么dp[k1]+k2就可以作为k1+1到k2这个区间的最小值，不需要遍历一个线性表，而只需要取这个单调队列的前两个值。同时也可以注意到这种做法表明只有在队列里至少有两个元素的时候转移可以成立，所以，当新值为最大值的时候可以特判一下从必要位置（因为mid的限制）出发到i的区间最小值，将其与multiset中的最小值进行比较，但是没必要入队（这里非常巧妙）。
Multiset的复杂度在NlogN左右，因此这题在复杂度32NlogN左右解决了。
做的时候顶级折磨，直到现在想起来还是觉得是个非常神奇的做法，单调队列优化dp的关键在于找到单调性（本题中的dp[i]递增以及k尽量小都是缺一不可的），充满了思维性。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 50005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
#define endl '\n'
#define cst 130000
using namespace std;
ll a[maxn],b[maxn],qzh[maxn];
ll qa[maxn], qr[maxn],na[maxn],nu[maxn];
ll minb[maxn], maxa[maxn];
int avlb[maxn];
ll blka[maxn], blkb[maxn],dp[maxn];
multiset<ll> st;
bool judge(ll mid,ll lmt,int xb) {
	if (qzh[xb - 1] < mid)return true;
	st.clear();
	int head = 0, tail = -1,bhead=1;
	ll arr = 0;
//	memset(dp, 0, sizeof(dp));
	inc(i, 1, xb + 1) {
		arr += blkb[i];
		while (arr > mid) {
			arr -= blkb[bhead];
			bhead++;
		}
		if (bhead > i)return false;
		while (head <= tail && blka[nu[tail]] <= blka[i]) {
			if (head < tail) {
				st.erase(dp[nu[tail-1]] + blka[nu[tail]]);
			}
			tail--;
		}
		tail++;
		nu[tail] = i;
		if (head < tail)st.insert(dp[nu[tail - 1]] + blka[nu[tail]]);
		while (head <= tail && nu[head] < bhead) {
			if (head < tail)st.erase(dp[nu[head]] + blka[nu[head + 1]]);
			head++;
		}
		dp[i] = dp[bhead - 1] + blka[nu[head]];
		if(head<tail)dp[i] = min(dp[i], *st.begin());
		//cout << "mid = " << mid << " dp." << i << " = " << dp[i] << endl;
		if (dp[i] > lmt)return false;
	}
	return true;
}
int main() { 
	cfast;
	ll n, lmt;
	cin >> n >> lmt;
	minb[0] = 1e9;
	inc(i, 1, n+1) {
		cin >> a[i]>>b[i];
		qzh[i] = qzh[i - 1] + b[i];
		minb[i] = min(minb[i - 1], b[i]);
	}
	for (int i = n; i >= 0; i--) {
		maxa[i] = max(maxa[i + 1], a[i]);
	}
	int xb = 1;
	int heada = 0, taila = -1;
	inc(i, 1, n + 1) {
		
		while (heada <= taila && a[i] >= qa[taila])taila--;
		taila++;
		qa[taila] = a[i];
		na[taila] = i;
		if (minb[i] > maxa[i + 1]) {
			avlb[xb] = i; 
			while (heada <= taila && na[heada] <= avlb[xb - 1])heada++;
			blka[xb] = qa[heada];
			blkb[xb] = qzh[i] - qzh[avlb[xb - 1]];
			xb++;
		}
	
	}
	if (xb == 2) {
		cout << blkb[1];
		return 0;
	}
	inc(i, 1, xb) {
	//	cout << "xb." << i << " with a = " << blka[i] << " and b = " << blkb[i] << endl;
		qzh[i] = qzh[i - 1] + blkb[i];
	}
	ll left = 1, right = (1 << 31)-1,ans=right;
	while (left <= right) {
		ll mid = (left + right) / 2;
		//cout << "mid=" << mid << endl;
		if (judge(mid, lmt, xb) == 1) {
			ans = min(ans, mid);
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	cout << ans << endl;

}
/*
3 7
2 9
5 8
7 15
*/