0%

受队友影响,也开始在博客更新自己补题的记录

(1/1000)

阅读全文 »

本文参照邓丝雨所写的dp进阶之路所作的笔记,在此%%邓丝雨姐姐

1.介绍

1.1 基本思想

​ dp的核心是对一类求最优解问题的算法,其核心是将一个问题分解成若干个子问题,通过每一次最优决策,求得出一个最优解。

1.2 适用条件

三点:

1.具有相同的子问题:首先,我们必须要保证这个问题能够分解出若干个子问题,并且能通过这些子问题来解决这个问题。

2.满足最优化原理(最优子结构):一个最优决策的子决策也是最优的。

3.具有无后效性:他要求每一个问题的决策,不能对未来问题产生影响,如果产生影响,就无法保证决策的最优性,这就是无后效性。

1.3 解题步骤

  1. 确定问题的子问题;

  2. 确定状态

  3. 推出状态转移方程(关键)

  4. 确定边界

  5. 优化

1.4 方法

  1. 根据dp的三要素,从而确定方向

1.1:先确定阶段的问题 :数塔问题

1.2 : 先确定状态的问题 :常见问题

1.3 : 先确定决策的问题 :背包问题


2. dp

2.1 线性dp

2.1.1 LIS问题

LIS问题即最长上升子序列(Longest increasing Sequence):给定一个长为N的数列A,求严格递增的子序列的最长长度是多少?

2.1.1.1 dp,O(n²)解法

首先每个单独的数列是一个子序列,长度为1,因此赋初值f[i]=1;

在此基础上,对i而言,设立一个j从最左扫描到i,去记录每一个比当前值a[i]小的数,通过f[i]来维护当前值。

以 {3 1 2 1 8 5 6}为例子

a[i] 3 1 2 1 8 5 6

len 1 1 2 1 3 3 4

对应的例子是

{3}

{1}

{1,2}

{1}

{1,2,8}

{1,2,5}

{1,2,5,6}

状态转移方程为:

$$\displaystyle dp[j]=\max_{1\leqslant i <j且len(i)<len(j)} dp[i]+1$$

1
2
3
4
5
6
7
8
for (int i = 1; i <= n; i ++ )
{
f[i] = 1;
for (int j = 1; j < i; j ++ )
if (a[i] > a[j])
f[i] = max(f[i], f[j] + 1);
res = max(res, f[i]);
}
2.1.1.2 贪心+二分 O(nlogn)解法

状态表示:dp[i]表示长度为i的上升子序列的最后一个元素的最小值,类似于维护最值的单调队列。

状态转移:

  • 若a[i] > a[len] ,那么dp[++len] = a[i],即把当前的元素追加到后面,使得上升子序列len+1。
  • 2反过来,则在dp中查找大于等于a[i]的第一个数的下标pos,令dp[pos] = a[i]。

最后结果就是dp[len](最长上升子序列的内容)

1
2
3
4
5
6
7
8
9
10
int n,dp[N],a[N];
int len=0;
for(int i=1;i<=n;i++)
{
if(a[i]>a[len]) a[++len] = a[i];
else
{
*lower_bound(dp+1,dp+len+1,a[i])=a[i];
}
}

lowbit

x&(-x)

树状数组

维护一个数组 a_1,..,a_n ,在 O(logn) 满足以下作用

1.单点加

2.查询前缀和

用c[n]来记录 其实应该满足$$\displaystyle c_i = a_{i - lowbit(i) + 1}$$

以前八个数来看就是:

c[1] = a[1]

c[2] = a[1] + a[2]

c[3] = a[3]

c[4] = a[1] + a[2] + a[3] + a[4]

c[5] = a[5]

c[6] = a[5] + a[6]

c[7] = a[7]

c[8] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8]

1.单点加

1
2
3
4
5
6
7
8
9
10
11
#define ll long long
const int N = 201000;
int a[N];
ll c[N];
ll query(int x){
ll s = 0;
for(; x; x -= x & (-x)){
s += c[x];
}
return s;
}

2.查询前缀和

1
2
3
4
5
6
7
8
9
#define ll long long
const int N = 201000;
int a[N];
ll c[N];
void modify(int x,ll s){
for(; x <= n; x += x & (-x)){
c[x] += s;
}
}

额外补充:

3.区间加的写法:

1.在区间 [l,r] 内的原数组a 加上 d

易知$$\displaystyle d_{i} = a_{i} - a_{i - 1}$$

如果对**[l , r]** 都加上 x,那么区间内差分数组实际上不会发生改变,实际上只有 $$\displaystyle d[l] += x,d[r + 1] -= x$$

coding:

1
2
3
4
5
6
7
int l,r;
long long d;
std::cin >> l >> r >> d;
c1.modify(l,d);
c1.modify(r + 1, -d);
c2.modify(l, l * d);
c2.modify(r + 1, (r + 1) * (-d));

2.在区间加的情况下进行查询

不难知道:

$$\displaystyle a_1 = d_1$$

$$\displaystyle a_2 = d_1 + d_2$$

$$\displaystyle a_3 = d_1 + d_2 + d_3$$

易发现规律:

$$\displaystyle sum = x * d_1 + (x - 1) d_2 +\cdots + d_x$$

$$\displaystyle = \sum_{i = 1} ^ {x} (x + 1 - i) d_ i$$

$$\displaystyle = (x + 1) * \sum_{i = 1} ^ {x} d_i - \sum_{i = 1} ^ {x} i* d_i$$

coding:

1
ll ans = (x + 1) * c1.query(x) - c2.query(x)

封装的板子如下:

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
template <class T>
class Fenwick {
const int n;
std::vector<T> a;
public:
Fenwick(int n) : n(n), a(n) { }
void add(int x, T v) {
assert(0 <= x < n);
x ++;
while (x <= n) {
a[x - 1] += v;
x += x & (-x);
}
}
T sum(int x) {
assert(0 <= x < n);
T ans = 0;
while (x > 0) {
ans += a[x - 1];
x -= x & (-x);
}
return ans;
}
T rangeSum(int l, int r) {
assert(0 <= l <= r < n);
return sum(r) - sum(l);
}
};
单点修改:
1
2
void f.add(int x,T v)
a[x] += p;

复杂度:O(logN)

区间查询(Sum):
1
T f.sum(int x)

查询 [0,x) 的区间和

时间复杂度:O(logN)

区间查询(rangeSum):
1
T f.rangeSum(int l, int r)

查询 [l,r) 的区间元素和

线段树

建树+查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int N = 201000;
struct node {
int minv;
} seg[N * 4];

void update(int id) {
seg[id].minv = std::min(seg[id * 2].minv, seg[id * 2 + 1].minv);
}

void build(int id,int l,int r){
if (l == r){
seg[id].minv = a[l];
} else {
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
update(id);
}
}
//build(1, 1, n);

单点修改

1
2
3
4
5
6
7
8
9
10
11
12
//节点为id,对应区间为[l,r],修改a[pos] -> val
void change(int id, int l, int r, int pos, int val) {
if(l == r){
seg[id].minv = val;
} else {
int mid = (l + r) / 2;
if(pos <= mid) change(id * 2, l, mid, pos, val);
else change(id * 2 + 1, mid + 1, r, pos, val);
update(id);
}
}
//change(1, 1, n, x, d);

查询最小值

1
2
3
4
5
6
7
8
9
10
int query(int id, int l, int r, int ql, int qr) {
if(l == ql && r == qr) return seg[id].minv;
int mid = l + r >> 1;
if(qr <= mid) return query(id * 2, l, mid, ql, qr);
else if(ql > mid) return query(id * 2 + 1, mid + 1, r, ql, qr);
else {
return std::min(query(id * 2, l, mid, ql, mid), query(id * 2 + 1, mid + 1, r, mid + 1, qr));
}
}
//query(1, 1, n, l, r);

懒标记