小编带你来了解下 dp：

结构#

线性#

区间#

背包#

树 & 图#

树形 dp#

P2279 消防局的设立#

方法一#

设 $f_{i,0/1/2/3/4}$ 为以 $i$ 为子树，保证能点亮下两层/下一层/自己/父亲/上二及以下的所有节点的最小代价。

转移比较简单。

方法二#

设 $f_{i,0/1/2/3/4}$ 为以 $i$ 为子树，存在 $i$ 的下下层儿子/儿子/自己/父亲/往上距离为 2 的点将其点亮的最小代价。

转移读者自行尝试，如果不会，可以去问连神，chm_qwq。

虽然不知道和方法一有什么区别。

方法三#

贪心，我们考虑在刚好能点亮的位置点灯。下面设 $D$ 为一个灯最远能点亮的距离。

于是设 $g_{i}$ 为以 $i$ 为子树最远没有被点亮的距离； $f_i$ 为以 $i$ 为子树最近被点亮的点的距离。

根据定义有： $g_i=\max_{i\in son_u} g_i+1$ ， $f_i=\min_{i\in son_u} f_i+1$ 。

于是分三种情况。

$g_i+f_i \le D$ ：可以直接点亮，于是 $g_i=-inf$ 。
如果这个点为必须点亮而没有被点亮，既 $f_i>D$ ，那么 $g_i=\max\{0,g_i\}$ 既要求其他点给这个点点亮。
若 $g_i=D$ 到最远距离了，直接在该点放灯塔，那么 $g_i=-inf,f_i=0$ 。

ex方法一/二#

若在点 $i$ 放灯要代价 $a_i$ 。

$f_{i,j}$ 为以 $i$ 为子树，向上至少能点亮 $j$ 层的最小代价。

$g_{i,j}$ 为以 $j$ 为子树，向下至少能点亮 $j$ 层的最小代价。

转移读者自推不难。

状压#

技巧#

枚举子集 $O(3^n)$ #

1
for(int T = (S - 1) & S;T;T = (T - 1) & S){
2
  //真子集要从S开始。
3
}

高维前缀和 $O(n 2^n)$ #

子集#

$g(S)=\sum_{T\subseteq S} f(T)$

eg： $f_s$ 表示有几个满足 $a_i \subseteq s$ 。

维护有三种理解。

去重法#

最简单的想法是去掉一个转移：

1
for(int j = 0;j < (1 << n);j++)
2
    for(int i = 0;i < n;i++)
3
    if(j >> i & 1) f[i] += f[i ^ (1 << j)];

然而会重，换枚举顺序即可。

1
for(int i = 0;i < n;i++)
2
  for(int j = 0;j < (1 << n);j++)
3
    if(j >> i & 1) f[i] += f[i ^ (1 << j)];

dp法#

为了去重，我们设 $f_{i,s}$ 表示只允许右 $i$ 位可与 $s$ 不同（但是仍为 $s$ 的子集）的和。

$f_{i,s}=f_{i-1,s}(i \not \in s)$
$f_{i,s}=f_{i-1,s} + f_{i-1,s \oplus 2^i}(i\in s)$

将 $i$ 滚掉即可得到代码。

类比法#

看三维前缀和：

1
for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) for(int z = 1;z <= n;z++)
2
    f[i][j][z] += f[i - 1][j][z];
3
for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) for(int z = 1;z <= n;z++)
4
    f[i][j][z] += f[i][j - 1][z];
5
for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) for(int z = 1;z <= n;z++)
6
    f[i][j][z] += f[i][j][z - 1];

若扩展到 $n$ 维也是如此。

假如每维只有 $2$ 呢，那么 $f$ 就可以状压成 $f_s$ ，然后枚举每一位即可。

超集#

$g(S)=\sum_{S\subseteq T} f(T)$

$f_s$ 表示有几个满足 $s \subseteq a_i$ 。

1
for(int i = 0;i < n;i++)
2
  for(int j = 0;j < (1 << n);j++)
3
    if(!(j >> i & 1)) f[i] += f[i ^ (1 << j)];

差分#

差分回去的话，直接把加号改成减号。

P3959 宝藏#

好题。核心技巧是枚举子集，妙处在状态设计。

因为加路径需要到起点的距离，那么我们可以看成一滴水从某个顶点开始散开，一次性添加需要的同一层的所有点。

于是我们先处理出 $f_{i,j}$ 表示当前点集为 $i$ ，扩展的点集为 $j$ 的最小路径长度和。

1
const int S = (1 << n) - 1;
2
for(int i = 2;i <= S;i++) lg[i] = lg[i >> 1] + 1;
3
for(int i = 1;i <= S;i++){
4
    cnt = 0;
5
    for(int j = (S ^ i) , _ = (S ^ i);j;j = (j - 1) & _)
6
        tmp[++cnt] = j;
7
    for(int j = cnt;j >= 1;j--){
8
        int lowbit = (tmp[j] & -tmp[j]) , v = inf;
9
        for(int z = 0;z < n;z++) if(i >> z & 1) v = min(v , mp[lg[lowbit]][z]);
10
        f[i][tmp[j]] = add(f[i][tmp[j] ^ lowbit] , v);
11
    }
12
}

然后求出 $g_{i,j}$ 表示共有 $i$ 层，点集为 $j$ ，显然 $g_{i,j}=\sum_{s\in j} g_{i-1,j\oplus s}+f_{j\oplus s,j}$ 。

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
using namespace std;
5

6
const int inf = 1e9;
7
int n , m;
8
int mp[20][20];
9
int f[4100][4100] , g[14][4100];
10
int lg[4100];
11
int tmp[4100] , cnt;
12

13
inline int add(int x , int y){ return (x > inf - y? inf : x + y); }
14
inline int mul(int x , int y){ return (x > inf / y? inf : x * y); }
15

16
int main(void){
17
  scanf("%d%d" , &n , &m);
18
  memset(mp , 0x3f , sizeof(mp));
19
  memset(g , 0x3f , sizeof(g));
20
  while(m--){
21
    int u , v , w; scanf("%d%d%d" , &u , &v , &w);
22
    u--; v--;
23
    mp[u][v] = min(mp[u][v] , w);
24
    mp[v][u] = min(mp[v][u] , w);
25
  }
26
  const int S = (1 << n) - 1;
27
  for(int i = 2;i <= S;i++) lg[i] = lg[i >> 1] + 1;
28
  for(int i = 1;i <= S;i++){
29
    cnt = 0;
30
    for(int j = (S ^ i) , _ = (S ^ i);j;j = (j - 1) & _)
31
      tmp[++cnt] = j;
32
    for(int j = cnt;j >= 1;j--){
33
      int lowbit = (tmp[j] & -tmp[j]) , v = inf;
34
      for(int z = 0;z < n;z++) if(i >> z & 1) v = min(v , mp[lg[lowbit]][z]);
35
      f[i][tmp[j]] = add(f[i][tmp[j] ^ lowbit] , v);
36
    }
37
  }
38
  // printf("%d\n" , f[1][8]);
39
  for(int i = 0;i < n;i++) g[0][1 << i] = 0;
40
  for(int k = 1;k < n;k++) for(int i = 1;i <= S;i++)
41
    for(int j = i;j;j = (j - 1) & i)
42
      g[k][i] = min(g[k][i] , add(g[k - 1][i ^ j] , mul(f[i ^ j][j] , k)));
43
  int ans = inf;
44
  for(int k = 0;k < n;k++) ans = min(ans , g[k][S]);
45
  printf("%d\n" , ans);
46
}

P1357 花园#

首先可以得： $f_{i,j}$ 为前 $i$ 个花后 $m$ 个为 $j$ 的方案，转移显然。环可以看成有 $n+m$ 朵花，前后相同。

然后发现 $f$ 均有前一状态转移而来，并且可转移的点相同，那么可以写成矩阵，矩阵快速幂优化即可。

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
using namespace std;
5
typedef long long ll;
6

7
const int MOD = 1e9 + 7;
8

9
ll n; int m , k , ans;
10

11
const int N = 32;
12
struct QWQ {
13
  int a[34][34];
14
  inline QWQ(){ memset(a , 0 , sizeof(a)); }
15
  inline friend QWQ operator * (const QWQ x , const QWQ y){
16
    QWQ ret;
17
    for(int i = 0;i < N;i++) for(int j = 0;j < N;j++)
18
      for(int k = 0;k < N;k++)
19
        if((ret.a[i][j] += (ll)x.a[i][k] * y.a[k][j] % MOD) >= MOD)
20
          ret.a[i][j] -= MOD;
21
    return ret;
22
  }
23
}base , qwq;
24

25
inline QWQ qpow(QWQ x , ll y){
26
  QWQ ret;
27
  for(int i = 0;i < N;i++) ret.a[i][i] = 1;
28
  while(y){
29
    if(y & 1) ret = ret * x;
30
    x = x * x; y >>= 1;
31
  }
32
  return ret;
33
}
34

35
int main(void){
36
  scanf("%lld%d%d" , &n , &m , &k);
37
  const int S = (1 << m) - 1;
38
  for(int j = 0;j <= S;j++){
39
    if(__builtin_popcount(j) > k) continue;
40
    base.a[(j << 1) & S][j] = 1;
41
    if(__builtin_popcount((j << 1 | 1) & S) <= k)
42
      base.a[(j << 1 | 1) & S][j] = 1;
43
  }
44
  qwq = qpow(base , n);
45
  for(int s = 0;s <= S;s++) if(__builtin_popcount(s) <= k)
46
    if((ans += qwq.a[s][s]) >= MOD) ans -= MOD;
47
  printf("%d\n" , ans);
48
}

P5369 [PKUSC2018] 最大前缀和#

难点在转换。

考虑枚举可能的最大前缀和，显然有 $2^n$ 种，对于每种合法的最大前缀和（前 $i$ 个为最大）：

$1<j \le i$ 满足 $\sum_{k=j}^i a_k \ge 0$ 。
$i < j \le n$ 满足 $\sum_{k=j}^i a_k < 0$ 。

原因显然。发现前后并不冲突，于是可以分开dp。

对于第一种，可以前插，条件是插入前的和大于等于 0。

对于第二种，可以后插，条件是插入后的和小于 0。

1
#include <cstdio>
2
#include <algorithm>
3
using namespace std;
4

5
const int MOD = 998244353;
6
int n , f[1100005] , g[1100005];
7
long long sum[1100005];
8
//f：后缀和的真子集都大于等于0的方案数
9
//g：前缀和都小于0的方案数
10

11
int main(void){
12
  scanf("%d" , &n);
13
  for(int i = 0;i < n;i++) scanf("%lld" , &sum[1 << i]);
14
  const int S = (1 << n) - 1;
15
  for(int s = 1;s <= S;s++) sum[s] = sum[s ^ (s & -s)] + sum[s & -s];
16
  g[0] = 1;
17
  for(int i = 0;i < n;i++) f[1 << i] = 1;
18
  for(int s = 0;s <= S;s++) for(int i = 0;i < n;i++){
19
    if(s >> i & 1) continue;
20
    if(sum[s] >= 0) (f[s | (1 << i)] += f[s]) %= MOD;
21
    if(sum[s | (1 << i)] < 0) (g[s | (1 << i)] += g[s]) %= MOD;
22
  }
23
  int ans = 0;
24
  for(int s = 0;s <= S;s++) (ans += ((sum[s] % MOD + MOD) % MOD) * f[s] % MOD * g[S ^ s] % MOD) %= MOD;
25
  printf("%d\n" , ans);
26
}

CF449D & P6442#

P6442：要求或起来为全集的方案数，不妨取反，于是变成求与起来为空集的方案数。

先求出 $f_s$ 表示有多少个数有 $s$ 。

然后 $g_s$ 表示与起来为 $s$ 超集的方案数，显然为 $2^{f_s}-1$ 。

然后差分回去就可以求出与起来为 $0$ 的方案数了。

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
using namespace std;
5
typedef long long ll;
6

7
const int MOD = 1e9 + 7;
8
int n , a[2000005];
9
ll f[2000005];
10

11
inline ll qpow(ll x , ll y){ ll ret = 1; while(y){ if(y & 1) ret = ret * x % MOD; x = x * x % MOD; y >>= 1; } return ret; }
12

13
int main(void){
14
  scanf("%d" , &n);
15
  for(int i = 1;i <= n;i++) scanf("%d" , &a[i]) , f[a[i]]++;
16
  const int S = (1 << 20) - 1;
17
  for(int i = 0;i < 20;i++) for(int j = 0;j <= S;j++)
18
    if(!(j >> i & 1)) f[j] += f[j ^ (1 << i)];
19
  for(int s = 0;s <= S;s++) f[s] = (qpow(2 , f[s]) - 1 + MOD) % MOD;
20
  for(int i = 0;i < 20;i++) for(int j = 0;j <= S;j++)
21
    if(!(j >> i & 1)) (f[j] += MOD - f[j ^ (1 << i)]) %= MOD;
22
  printf("%lld\n" , f[0]);
23
}

CF1208F#

比较喵的一道题。

可以枚举第一个数，考虑最大化，于是贪心从高位取。

每次判断是否存在两个不同且下标大于 i 的数的与是当前枚举的超集。

这个可以用高维前缀和预处理。

$f_s$ 表示为 $s$ 超集的下标最大值与次大值。

1
#include <cstdio>
2
#include <algorithm>
3
using namespace std;
4

5
int n , a[1000005];
6

7
struct QWQ {
8
  int a , b; //a > b
9
  inline QWQ(int _ = 0 , int __ = 0){ a = _; b = __; }
10
  inline QWQ friend operator + (const QWQ p , const QWQ q){
11
    if(p.a < q.a) return QWQ(q.a , max(p.a , q.b));
12
    return QWQ(p.a , max(p.b , q.a));
13
  }
14
}f[2097154];
15

16
int main(void){
17
  scanf("%d" , &n);
18
  for(int i = 1;i <= n;i++){
19
    scanf("%d" , &a[i]);
20
    f[a[i]] = f[a[i]] + QWQ(i , 0);
21
  }
22
  const int S = (1 << 21) - 1;
23
  for(int i = 0;i < 21;i++) for(int s = 0;s <= S;s++)
24
    if(!(s >> i & 1)) f[s] = f[s] + f[s ^ (1 << i)];
25
  int ans = 0;
26
  for(int i = 1;i <= n - 2;i++){
27
    int nw = 0;
28
    for(int j = 20;j >= 0;j--){
29
      if(a[i] >> j & 1) continue;
30
      if(f[nw | (1 << j)].b > i) nw |= (1 << j);
31
    }
32
    ans = max(ans , (nw | a[i]));
33
  }
34
  printf("%d\n" , ans);
35
}

计数 & 概率#

形式#

括号 :(#

看成(..)(..)(..)...和(...)dp
拆第一个成对括号，然后剩下的是同样的形式。
(看成 1，)看成 -1。前缀和非负。

基环树#

前置：树形dp

这是非树，但是有很好的性质的特殊图，他删掉一条边可以变为树，而且有且仅有一个环。

只要满足一个联通块内恰好有 n 条边，那么这个联通块就是基环树。

一般有两种 dp 方法：

是环#

由于只有一个环，那么直接将环缩成点，就是树了，最后再在环上特殊处理即可。

是边#

删掉一条边即可变为树，于是先删掉一条反祖边，树形 dp，特殊处理。

技巧#

用并查集找反祖边。
dfs找环。

小试#

a. P4381 Island#

可以转换成基环树求直径问题。

定义：基环树的直径为基环树上最长路径，非两点间最短路径。

首先找出环，标记出来，这样就有了若干棵子树，对每棵子树求直径和从根节点出发的最长路径。

如果把最长路径当做环的点权，那么问题就变成在环上找一条路径，路径权值为经过点权和与路径和，不能重复走点，求最长路径。

显然，断环成链，把节点复制一份，把边权算到右边的点权上，这样就变成最大区间和了，单调队列即可做。

（偷了张博客的图。。）

1
#include <cstdio>
2
#include <algorithm>
3
#include <vector>
4
#include <algorithm>
5
using namespace std;
6
typedef long long ll;
7

8
struct ZBJ { int x , w , id; };
9
vector <ZBJ> g[1000005];
10

11
int n;
12

13
int _f[1000005]; pair <int , int> ni[1000005]; int ni_cnt;
14
int find(int x){ return _f[x] == x? x : _f[x] = find(_f[x]); }
15

16
int huan[1000005] , onhuan[1000005] , tot;
17
ll a[2000005] , b[2000005];
18
bool find_huan(int x , int lt){
19
  if(huan[x] == 2){ return 1; }
20
  huan[x] = 2;
21
  for(ZBJ nxt : g[x]) if(nxt.id != lt){
22
    if(find_huan(nxt.x , nxt.id)){
23
      huan[x] = 1; onhuan[++tot] = x;
24
      b[tot] = nxt.w;
25
      return 1;
26
    }
27
  }
28
  huan[x] = -1;
29
  return 0;
30
}
31

32
ll ansd;
33
pair <ll , ll> dp[1000005]; //直径
34
void dfs(int x , int lt){
35
  dp[x] = {0 , 0};
36
  for(ZBJ nxt : g[x]) if(nxt.id != lt && huan[nxt.x] != 1){
37
    dfs(nxt.x , nxt.id);
38
    const ll t1 = dp[nxt.x].first + nxt.w;
39
    if(t1 >= dp[x].first)
40
      dp[x].second = dp[x].first , dp[x].first = t1;
41
    else if(t1 > dp[x].second)
42
      dp[x].second = t1;
43
  }
44
  ansd = max(ansd , dp[x].first + dp[x].second);
45
}
46

47
pair <ll , int> q[1000005]; int tl , hd;
48
inline ll solve(int x){
49
  ansd = 0; tot = 0; hd = 1; tl = 0;
50
  find_huan(ni[x].first , 0);
51
  for(int i = 1;i <= tot;i++){
52
    dfs(onhuan[i] , 0);
53
    a[i + tot] = a[i] = dp[onhuan[i]].first;
54
    // if(n == 15) printf("%d %d\n" , onhuan[i] , a[i]);
55
  }
56
  b[tot + 1] = b[1];
57
  b[1] = 0;
58
  for(int i = 2;i < tot;i++) b[i + tot] = b[i];
59
  int m = tot + tot - 1;
60
  // for(int i = 1;i <= m;i++) printf("%d:%d %d\n" , i , a[i] , b[i]);
61
  // puts("");
62
  for(int i = 1;i <= m;i++) b[i] += b[i - 1];
63

64
  ll ret = ansd;
65
  for(int i = 2;i <= tot;i++){
66
    while(tl >= hd && q[tl].first <= b[i] + a[i]) tl--;
67
    q[++tl] = {b[i] + a[i] , i};
68
  }
69
  for(int i = 1;i <= tot;i++){
70
    while(tl >= hd && q[hd].second <= i) hd++;
71
    // printf("%d\n" , q[hd].first);
72
    ret = max(ret , a[i] - b[i] + q[hd].first);
73
    while(tl >= hd && q[tl].first <= b[i + tot] + a[i + tot]) tl--;
74
    q[++tl] = {b[i + tot] + a[i + tot] , i + tot};
75
  }
76
  for(int i = 0;i <= m + 1;i++) a[i] = b[i] = 0;
77
  // printf("ret%d\n" , ret);
78
  return ret;
79
}
80

81
int main(void){
82
  scanf("%d" , &n);
83
  for(int i = 1;i <= n;i++) _f[i] = i;
84
  for(int i = 1 , v , w;i <= n;i++){
85
    scanf("%d%d" , &v , &w);
86
    g[i].push_back((ZBJ){v , w , i});
87
    g[v].push_back((ZBJ){i , w , i});
88
    if(find(i) == find(v)){ ni[++ni_cnt] = {i , v}; continue; }
89
    _f[find(i)] = find(v);
90
  }
91
  ll ans = 0;
92
  for(int i = 1;i <= ni_cnt;i++) ans += solve(i);
93
  printf("%lld\n" , ans);
94
}

b. P2607 骑士#

比较简单，因为不保证联通，于是是基环森林，每个联通快都是 n 条边，于是是基环树。

又因为相互没有影响，于是分开考虑。发现当成树的子问题是最大独立集，简单树形 dp 可做，再考虑反祖边，这两点不能同时选，那么强制某个点不选再取最大即可。

排列类#

https://www.luogu.com.cn/article/xt2szowt

直接按照下标转移的暂时不说。

插入法#

我们按照值从小到大插入，即 $f_i$ 表示插入了小于等于 $i$ 的所有数的答案。

AT_dp_t Permutation#

$f_{i,j}$ 表示前 $i$ 个，前一个插的排名为 $j$ ，转移不难。

连续段dp#

https://www.cnblogs.com/chroneZ/p/17938137

https://www.cnblogs.com/stinger/p/16471744.html

https://www.cnblogs.com/best-brain/p/18006547

有点像扫描线，我们以加入顺序为横轴，位置为纵轴画如上图，然后按照大小顺序从下往上扫（上往下，下往上都可）。

我们把连在一起的称为一个连续段，连续段 dp 是通过连续段的数量来进行 dp。

有以下三种情况。

延伸(2->2) 新建(2->3)

好像不对。。。

P5999 [CEOI 2016] kangaroo#

求波浪型排列（其差分正负交错，没有连续的正或负），满足 $p_1=s,p_n=t$ 的方案数。

显然可以从小往大插，设 $f_{i,j}$ 表示插入了前 $i$ 个数，形成了 $j$ 个段的方案数。

我们枚举 $i(i\not = s,i \not = t)$ 。

新建段：

对于 $f_{i-1,j-1}$ ，它有 $j$ 个空位，当我们放入 $i$ 时，显然比之前放的都大，这里没啥限制，都是合法的。

唯一的限制是 $p_1=s,p_n=t$ ，所以当 $i+1>s$ 时， $p_1$ 被放了，空位减，尾同理。

所以 $(j-[i>s]-[i>t])f_{i-1,j-1} \to f_{i,j}$ 。

段添加：

我们不能允许这种操作，因为如果允许了，因为只能往块的头尾加，这样一定不满足波浪型限制，不必转移。

段合并：

无论放哪，两侧相邻的都比 $i$ 小，合成的新的块仍满足此性质。

$jf_{i-1,j+1} \to f_{i,j}$ 。

答案即为 $f_{n,1}$ 。

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
using namespace std;
5

6
const int MOD = 1e9 + 7;
7
int n , s , t;
8
int f[2005][2005];
9

10
int main(void){
11
  scanf("%d%d%d" , &n , &s , &t);
12
  f[0][0] = 1;
13
  for(int i = 1;i <= n;i++) for(int j = 1;j <= i;j++){
14
    if(i == s || i == t){
15
      f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % MOD;
16
      continue;
17
    }
18
    f[i][j] = (1LL * j * f[i - 1][j + 1] % MOD + 1LL * (j - (i > s) - (i > t)) * f[i - 1][j - 1] % MOD) % MOD;
19
  }
20
  printf("%d\n" , f[n][1]);
21
}

CF1515E#

设 $f_{i,j}$ 加入了前 $i$ 个点，一共有 $j$ 个连续段。

新建： $f_{i,j}\times(j+1)\longrightarrow f_{i+1,j+1}$ $f_{i, j} \times (j + 1) ⟶ f_{i + 1, j + 1}$ 。
- 系数：有 $(j+1)$ 个空位。
- 为什么能加：不知道

优化#

单调队列#

决策单调性#

https://www.cnblogs.com/alex-wei/p/DP_optimization_method_II.html

https://www.cnblogs.com/birchtree/p/12937975.html

四边形不等式#

定义1：若对于 $\forall a\le b \le c \le d$ ，满足 $w(a,d)+w(b,c)\ge w(a,c)+w(b,d)$ 。则称 $w$ 满足四边形不等式。

下面的推论比较好用。

推论1.1：对于 $\forall a < b$ ，满足 $w(a,b+1)+w(a+1,b)\ge w(a,b)+w(a+1,b+1)$ 则 $w$ 满足四边形不等式。

证明：设 $a<c,a+1<c$ 可得两式，相加可证 $a<b<c,w(a,c+1)+w(b,c)\ge w(a,c)+w(b , c+1)$ ，同样可证出

$w(a,d)+w(b,c)\ge w(a,c)+w(b,d)$ ，所以满足四边形不等式。

推论1.2：若 $w$ 满足四边形不等式，那么 $w$ 满足凸完全单调性，即 $w$ 是凸函数。

从四边形不等式到决策单调性#

定义2：对于 $f_i=\min\{f_j+w(j,i)| 0 \le j < i\}$ 的状态转移方程，若 $j=p_i$ 时可让 $f_i$ 取得最小值，则 $p_i$ 为 $f_i$ 的最优决策点。若 $p_i$ 单调不降，那么称 $f$ 具有决策单调性。

定理2.1：若 $w$ 满足四边形不等式，那么 $f$ 具有决策单调性。

证明：

$\forall i \in [1,n],j\in[0,p_i)$ ，根据 $p_i$ 的定义得： $f_{p_i}+w(p_i,i)\le f_j+w(j,i)\tag 1$

$\forall i'\in(i,n]$ ，此时 $j<p_i<i<i'$ ，所以 $w(j,i')+w(p_i,i)\ge w(j,i)+w(p_i,i')$

移项得： $w(p_i,i')-w(p_i,i)\le w(j,i')-w(j,i) \tag 2$

$(1)+(2)$ 得： $f_{p_i}+w(p_i,i')\le f_j+w(j,i')$

所以 $j<p_i$ 的一定没有决策点 $p_i$ 优，于是 $f_{i'}$ 的最优决策点 $p_{i'}\ge p_i$ ，所以 $f$ 具有决策单调性。

大胆假设#

一般题目可以通过枚举（瞎猜）来验证四边形不等式，无需严格证明。

然后你就拥有了一个很强的性质：决策单调性。于是你可以使用以下几种方式优化成 $O(n\log n)$

以分治#

适用范围： $f$ 转移不与当前层的 $f$ 有关。

比较简单的想法，由于决策单调性，所以对于 $f_i$ 可能的决策点是一个区间。

可以利用分治先求出 $f_{mid}$ 再求出左右区间的决策点范围。

1
void solve(int l , int r , int ql , int qr){
2
  int mid = (l + r) >> 1 , k = ql;
3
  for(int i = ql , _ = min(mid - 1 , qr);i <= _;i++) if(v(i , mid) > p[mid])
4
    p[mid] = v(i , mid) , k = i;
5
  if(l < mid) solve(p , l , mid - 1 , ql , k);
6
  if(mid < r) solve(p , mid + 1 , r , k , qr);
7
}

以二分队列#

适用范围：决策点单调不降。

考虑每个点可能作为最优决策点的范围，容易证明一定成区间。

我们可以用 $(x,l,r)$ 表示决策点 $x$ 可能作为 $[l,r]$ 的 $f$ 的最优决策点，放进队列里。

然后分三步：

无法成为 $f_i$ 的最优决策点的出队列。
更新 $f_i$ 。
出队。
1. 加入队尾严格劣于 $i$ ，那么这个决策点一定不优。这里可以通过对 $l$ 的贡献大小判断。
2. 空队列，直接加 $(i,i+1,n)$ 。
3. 如果队尾部分优于 $i$ ，那么需要修改队尾的区间。由于区间连续，则一定存在一点满足左边队尾优，右边 $i$ 优，那么可以二分找出来。

1
struct SB{ int x,  l , r; };
2
deque <SB> q;
3
q.push_back((SB){0 , 1 , n});
4
for(int i = 1;i <= n;i++){
5
    while(!q.empty() && q.front().r < i) q.pop_front();
6
    q.front().l = i;
7
    f[i] = v(p[i] = q.front().x , i);
8
    while(!q.empty() && v(i , q.back().l) <= v(q.back().x , q.back().l)) q.pop_back();
9
    if(q.empty()){ q.push_back((SB){i , i + 1 , n}); continue; }
10
    int l = q.back().l , r = q.back().r + 1 , ret = r;
11
    while(l <= r){
12
        int mid = (l + r) >> 1;
13
        if(v(i , mid) <= v(q.back().x , mid)){ ret = mid; r = mid - 1; }
14
        else l = mid + 1;
15
    }
16
    if(ret <= n){
17
        q.back().r = ret - 1;
18
        q.push_back((SB){i , ret , n});
19
    }
20
}

以二分栈#

斜率优化#

一些只和 $i,j$ 有关的项和一个和 $i,j$ 都有关的项的和，一般可以使用斜率优化。

例如：

$f_i=\max\{f_j+a_i+a_j+b_ib_j\}$

假如 $i$ 一定，可以看成关于 $j$ 的函数。

$f_i-a_i-b_ib_j=f_j+a_j$

观察 $b+kx=y$ ，得：

$b=f_i-a_i,k=-b_i,x=b_j,y=f_j+a_j$

现在已知所有的 $(x,y)$ ，要求出最大的 $f_i=b+a_i$ ，因为 $a_i,k$ 是常数，所以相当于找最大的 $b$ 使得直线能经过一个点 $(x,y)$ 。

尝天下鲜#

P1912 小G诗人#

设 $s_i=i+\sum |s_j|$

所以 $f_i=\min\{f_j+|s_i-s_j-1-L|^P\}$

猜测满足四边形不等式，于是具有决策单调性。

所以直接用二分队列优化就行了。

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
#include <queue>
5
using namespace std;
6
typedef long double ll;
7

8
const ll MAX = 1000000000000000007;
9
int T , n , L , P;
10

11
char str[3200005]; int  _;
12
struct ZBj{
13
  int st , le;
14
  inline void read(){
15
    st = _;
16
    scanf("%s" , str + st);
17
    le = strlen(str + st);
18
//    printf("%d %d %s\n" , _ , le , str + st);
19
    _  += le + 2;
20
  }
21
}a[100005]; int s[100005];
22
ll f[100005]; int p[100005];
23

24
inline ll mul(ll x , ll y){ return x * y; }
25
inline ll add(ll x , ll y){ return x + y; }
26

27
inline ll qpow(ll x , int y){
28
  if(x == 0) return 0;
29
  ll ret = 1;
30
  while(y){
31
    if(y & 1) ret = mul(ret , x);
32
    x = mul(x , x); y >>= 1;
33
  }
34
  return ret;
35
}
36

37
inline ll v(int j , int i){ return add(f[j] , qpow(abs(s[i] - s[j] - 1 - L) , P)); }
38

39
void print(int x){
40
  if(x <= 0) return ;
41
  print(p[x]);
42
  for(int i = p[x] + 1;i <= x;i++) printf("%s%c" , str + a[i].st , i == x? '\n' : ' ');
43
}
44

45
struct SB{ int x,  l , r; };
46
deque <SB> q;
47
inline void solve(){
48
  _ = 0;
49
  scanf("%d%d%d" , &n , &L , &P);
50
  for(int i = 1;i <= n;i++) a[i].read();
51
  for(int i = 1;i <= n;i++) s[i] = s[i - 1] + a[i].le + 1;
52
  f[0] = 0;
53
  q.clear();
54
  q.push_back((SB){0 , 1 , n});
55
  for(int i = 1;i <= n;i++){
56
    while(!q.empty() && q.front().r < i) q.pop_front();
57
    q.front().l = i;
58
    f[i] = v(p[i] = q.front().x , i);
59
    while(!q.empty() && v(i , q.back().l) <= v(q.back().x , q.back().l)) q.pop_back();
60
    if(q.empty()){ q.push_back((SB){i , i + 1 , n}); continue; }
61
    int l = q.back().l , r = q.back().r + 1 , ret = r;
62
    while(l <= r){
63
      int mid = (l + r) >> 1;
64
//      printf("%d %d %d\n" , mid , q.back().x , i);
65
      if(v(i , mid) <= v(q.back().x , mid)){ ret = mid; r = mid - 1; }
66
      else l = mid + 1;
67
    }
68
    if(ret <= n){
69
      q.back().r = ret - 1;
70
      q.push_back((SB){i , ret , n});
71
    }
72
  }
73
  if(f[n] > 1000000000000000000) puts("Too hard to arrange");
74
  else{
75
    printf("%.0LF\n" , f[n]);
76
    print(n);
77
  }
78
  puts("--------------------");
79
}
80

81
int main(void){
82
//  freopen("awa.in" , "r" , stdin);
83
  int T; scanf("%d" , &T);
84
  while(T--) solve();
85
}

P5503 灯塔#

显然可以翻转序列做两遍。

$p_i=\max\{h_j+\sqrt{i-j}-h_i\}$

可以证明有决策单调性，用分治优化。

1
#include <cstdio>
2
#include <cmath>
3
#include <algorithm>
4
using namespace std;
5

6
int n , h[500005];
7
double p1[500005] , p2[500005];
8

9
void solve(double p[500005] , int l , int r , int ql , int qr){
10
  int mid = (l + r) >> 1 , k = ql;
11
  for(int i = ql , _ = min(mid - 1 , qr);i <= _;i++)
12
    if(h[i] + __builtin_sqrt(mid - i) - h[mid] > p[mid])
13
      p[mid] = h[i] + __builtin_sqrt(mid - i) - h[mid] , k = i;
14
  if(l < mid) solve(p , l , mid - 1 , ql , k);
15
  if(mid < r) solve(p , mid + 1 , r , k , qr);
16

17
}
18

19
int main(void){
20
  scanf("%d" , &n);
21
  for(int i = 1;i <= n;i++) scanf("%d" , &h[i]);
22
  //p = max(h[j]+sqrt(i-j))-h[i]
23
  solve(p1 , 1 , n , 1 , n);
24
  reverse(h + 1 , h + 1 + n);
25
  solve(p2 , 1 , n , 1 , n);
26
  for(int i = 1;i <= n;i++) printf("%.0lf\n" , ceil(max(p1[i] , p2[n - i + 1])));
27
}

slope trick#

线段树#

凸优化#

wqs 二分#

WQS 二分通常用于解决这样一类优化问题：它们带有数量限制，直接求解代价较高；但一旦去除这一限制，问题本身就变得容易得多。

并且要求为凸函数。

一般的，可以二分选择的代价惩罚，然后根据找到一个代价，使得刚好选到要求的个数。

邮局加强版加强版#

二分放邮局的代价，用四边形不等式优化 $O(n\log n)$ 算出最优解，然后调整即可。

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
#include <queue>
5
using namespace std;
6
typedef long long ll;
7

8
int n , m , a[500005]; ll sum[500005];
9

10
inline ll w(int l , int r){
11
  int mid = (l + r) >> 1;
12
  return 1LL * (mid - l) * a[mid] - (sum[mid - 1] - sum[l - 1]) + (sum[r] - sum[mid]) - 1LL * (r - mid) * a[mid];
13
}
14

15
struct ZBJ { int x , l , r; };
16
deque <ZBJ> q;
17

18
pair <ll , int> f[500005];
19

20
inline ll v(int x , int y){ //x -> y
21
  return f[x].first + w(x + 1 , y);
22
}
23

24
inline ll solve(ll mid){
25
  // memset(f , 0x3f , sizeof(f));
26
  while(!q.empty()) q.pop_front();
27
  f[0] = {0 , 0};
28
  q.push_back((ZBJ){0 , 1 , n});
29
  for(int i = 1;i <= n;i++){
30
    while(!q.empty() && q.front().r < i) q.pop_front();
31
    q.front().l = i;
32
    f[i] = {v(q.front().x , i) + mid , f[q.front().x].second + 1};
33
    while(!q.empty() && v(i , q.back().l) <= v(q.back().x , q.back().l))
34
      q.pop_back();
35
    if(q.empty()){ q.push_back((ZBJ){i , i + 1 , n}); continue; }
36
    int l = q.back().l , r = q.back().r + 1 , ret = r;
37
    while(l <= r){
38
      int mi = (l + r) >> 1;
39
      if(v(i , mi) <= v(q.back().x , mi)){
40
        ret = mi;
41
        r = mi - 1;
42
      }
43
      else l = mi + 1;
44
    }
45
    if(ret <= n){
46
      q.back().r = ret - 1;
47
      q.push_back((ZBJ){i , ret , n});
48
    }
49
  }
50
  return f[n].second;
51
}
52

53
int main(void){
54
  scanf("%d%d" , &n , &m);
55
  for(int i = 1;i <= n;i++) scanf("%d" , &a[i]);
56
  sort(a + 1 , a + 1 + n);
57
  for(int i = 1;i <= n;i++) sum[i] = sum[i - 1] + a[i];
58
  ll l = 0 , r = 1e12 , ret;
59
  while(l <= r){
60
    ll mid = (l + r) >> 1;
61
    if(solve(mid) >= m){
62
      ret = mid;
63
      l = mid + 1;
64
    }
65
    else r = mid - 1;
66
  }
67
  solve(ret);
68
  printf("%lld\n" , f[n].first - ret * m);
69
}

P5896 [IOI 2016] aliens#

大约可以看成线段覆盖问题。

首先按照线段 $l$ 排序，将完全被其他线段包含的去掉（显然对答案没有贡献）。

画图可知，设 $f_i$ 位覆盖前 $i$ 个线段的最小代价。

于是 $f_i=\min \{ f_j+(r_i - l_{j+1}+1)^2-\max\{r_j-l_{j+1}+1\}^2\}$ 。

用 wqs 二分即可做到 41 分。

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
#include <algorithm>
5
using namespace std;
6
typedef long long ll;
7

8
inline ll sqr(int x){ return 1LL * x * x; }
9

10
int n , m , k;
11

12
struct Line {
13
  int l , r;
14
  inline bool operator < (const Line b){ if(l == b.l) return r > b.r; return l < b.l; }
15
}qwq[1000005]; ll g[1000005];
16

17
pair <ll , int> f[1000005];
18
inline int solve(ll mid){
19
  memset(f , 0x3f , sizeof(f));
20
  f[0] = {0 , 0};
21
  for(int i = 1;i <= n;i++)
22
    for(int j = 0;j < i;j++)
23
      f[i] = min(f[i] , {f[j].first - g[j] + sqr(qwq[i].r - qwq[j + 1].l + 1) + mid , f[j].second + 1});
24
  return f[n].second;
25
}
26

27
int main(void){
28
  scanf("%d%d%d" , &n , &m , &k);
29
  if(n >= 50000){ puts("NO"); return 0; }
30
  for(int i = 1;i <= n;i++){
31
    scanf("%d%d" , &qwq[i].l , &qwq[i].r);
32
    qwq[i].l++; qwq[i].r++;
33
    if(qwq[i].l > qwq[i].r) swap(qwq[i].l , qwq[i].r);
34
  }
35
  sort(qwq + 1 , qwq + 1 + n);
36
  int chm_qwq = 0;
37
  for(int i = 1 , r = -1;i <= n;i++)
38
    if(qwq[i].r > r){ r = qwq[i].r; qwq[++chm_qwq] = qwq[i]; }
39
  n = chm_qwq;
40
  for(int i = 1;i < n;i++) g[i] = sqr(max(qwq[i].r - qwq[i + 1].l + 1 , 0));
41
  ll l = 0 , r = 1e12 , ret = -114514;
42
  while(l <= r){
43
    ll mid = (l + r) >> 1LL;
44
    if(solve(mid) <= k){
45
      ret = mid;
46
      r = mid - 1;
47
    }
48
    else l = mid + 1;
49
  }
50
  solve(ret);
51
  printf("%lld\n" , f[n].first - ret * k);
52
}

然后再对 $f$ 斜率优化即可 AC

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
#include <algorithm>
5
using namespace std;
6
typedef long long ll;
7

8
inline ll sqr(int x){ return 1LL * x * x; }
9

10
int n , m , k;
11

12
struct Line {
13
  int l , r;
14
  inline bool operator < (const Line b){ if(l == b.l) return r > b.r; return l < b.l; }
15
}qwq[1000005]; ll g[1000005];
16

17
int q[1000005] , hd , tl;
18
pair <ll , int> f[1000005];
19

20
inline ll Y(int x){ return f[x].first - g[x] + sqr(qwq[x + 1].l); }
21
inline ll X(int x){ return qwq[x + 1].l; }
22
inline long double count(int x , int y){ return (long double)(Y(x) - Y(y)) / (X(x) - X(y)); }
23

24
inline int solve(ll mid){
25
  q[hd = tl = 1] = 0;
26
  for(int i = 1;i <= n;i++){
27
    while(tl > hd && count(q[hd] , q[hd + 1]) < 2 * qwq[i].r) hd++;
28
    const int j = q[hd];
29
    f[i] = {f[j].first - g[j] + sqr(qwq[i].r - qwq[j + 1].l) + mid , f[j].second + 1};
30
    while(tl > hd && count(q[tl - 1] , q[tl]) > count(q[tl] , i)) tl--;
31
    q[++tl] = i;
32
  }
33
  // for(int i = 1;i <= n;i++)
34
  //   for(int j = 0;j < i;j++)
35
  //     f[i] = min(f[i] , {f[j].first - g[j] + sqr(qwq[i].r - qwq[j + 1].l + 1) + mid , f[j].second + 1});
36
  return f[n].second;
37
}
38

39
int main(void){
40
  scanf("%d%d%d" , &n , &m , &k);
41
  for(int i = 1;i <= n;i++){
42
    scanf("%d%d" , &qwq[i].l , &qwq[i].r);
43
    if(qwq[i].l > qwq[i].r) swap(qwq[i].l , qwq[i].r);
44
  }
45
  sort(qwq + 1 , qwq + 1 + n);
46
  int chm_qwq = 0;
47
  for(int i = 1 , r = -1;i <= n;i++)
48
    if(qwq[i].r > r){ r = qwq[i].r; qwq[++chm_qwq] = qwq[i]; }
49
  n = chm_qwq;
50
  for(int i = 1;i < n;i++) g[i] = sqr(max(qwq[i].r - qwq[i + 1].l + 1 , 0));
51
  for(int i = 1;i <= n;i++) qwq[i].r++;
52
  ll l = 0 , r = 1e12 , ret = -114514;
53
  while(l <= r){
54
    ll mid = (l + r) >> 1LL;
55
    if(solve(mid) <= k){
56
      ret = mid;
57
      r = mid - 1;
58
    }
59
    else l = mid + 1;
60
  }
61
  solve(ret);
62
  // printf("qwq%d %d\n" , ret , solve(ret));
63
  printf("%lld\n" , f[n].first - ret * k);
64
}

矩阵#

技巧：边权小时可以拆点，变成边权为 1。

P6569#

模板，主要是满不满足结合律不好证。

我也不会证明。。

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
using namespace std;
5
typedef long long ll;
6

7
int n , m , q;
8

9
int N;
10
struct ZBJ {
11
  ll a[102][102];
12

13
  inline void clear(){ for(int i = 1;i <= N;i++) for(int j = 1;j <= N;j++) a[i][j] = 0; }
14

15
  inline friend ZBJ operator * (const ZBJ x , const ZBJ y) {
16
    ZBJ ret; ret.clear();
17
    for(int i = 1;i <= N;i++) for(int j = 1;j <= N;j++)
18
      for(int k = 1;k <= N;k++)
19
        ret.a[i][j] ^= x.a[i][k] * y.a[k][j];
20
    return ret;
21
  }
22
}A[35];
23

24
ll f[105] , tmp[105];
25

26
inline void mul(ll k){
27
  for(int _ = 0;_ < 32;_++) if(k >> _ & 1){
28
    for(int i = 1;i <= N;i++) tmp[i] = f[i];
29
    for(int i = 1;i <= N;i++) f[i] = 0;
30
    for(int j = 1;j <= N;j++) for(int k = 1;k <= N;k++)
31
      f[j] ^= tmp[k] * A[_].a[k][j];
32
//      printf("%d %d %d %d %d\n" , j , k , f[j] , tmp[j] , A[_].a[k][j]);
33
  }
34
}
35

36
pair <ll , int> qqq[105]; ll ans[105];
37

38
int main(void){
39
  scanf("%d%d%d" , &n , &m , &q); N = n;
40
  for(int i = 1;i <= n;i++) scanf("%lld" , &f[i]);
41
  for(int i = 0;i < 32;i++) A[i].clear();
42
  while(m--){
43
    int u , v; scanf("%d%d" , &u , &v);
44
    A[0].a[u][v] = A[0].a[v][u] = 1;
45
  }
46
  for(int i = 1;i <= q;i++) scanf("%lld" , &qqq[i].first) , qqq[i].second = i;
47
  sort(qqq + 1 , qqq + 1 + q);
48
  for(int i = 1;i < 32;i++) A[i] = A[i - 1] * A[i - 1];
49
  ll lt = 0;
50
  for(int i = 1;i <= q;i++){
51
    mul(qqq[i].first - lt); lt = qqq[i].first;
52
    ans[qqq[i].second] = f[1];
53
  }
54
  for(int i = 1;i <= q;i++) printf("%lld\n" , ans[i]);
55
}

P6772#

这题很容易写出 $f_{v,j}=\max\{ f_{i,j-w}+c_v\}$ ，这还不是很符合 $(\max,+)$ 矩阵。

发现 $w\le 5$ ，很小，拆边边太多了，于是拆点，每个点拆成 5 个，连边就可以连 $(u,w)$ 和 $(v,1)$ 就可以了。

这样没条边的边权都为 1 了，直接放到矩阵上，点数为 $5n$ 。

但是这样无法处理节日，因此可以分段，按照时间排个序，然后按照上题的方法优化，跑完后更新。

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
using namespace std;
5
typedef long long ll;
6
#define ID(x , k) ((x) + (k - 1) * n)
7

8
const ll inf = 1e16;
9
int n , m , T , k; ll a[255];
10

11
int N;
12
struct ZBJ {
13
  ll a[252][252];
14

15
  inline void clear(){ for(int i = 1;i <= N;i++) for(int j = 1;j <= N;j++) a[i][j] = -inf; }
16

17
  inline friend ZBJ operator * (const ZBJ x , const ZBJ y) {
18
    ZBJ ret; ret.clear();
19
    for(int i = 1;i <= N;i++) for(int j = 1;j <= N;j++)
20
      for(int k = 1;k <= N;k++)
21
        ret.a[i][j] = max(ret.a[i][j] , x.a[i][k] + y.a[k][j]);
22
    return ret;
23
  }
24
}A[31];
25

26
ll f[2][252];
27

28
inline void mul(int k , int nw , int lt){
29
  for(int _ = 0;_ < 30;_++) if(k >> _ & 1){
30
    for(int i = 1;i <= N;i++) f[nw][i] = -inf;
31
    for(int i = 1;i <= N;i++) for(int j = 1;j <= N;j++)
32
      f[nw][i] = max(f[nw][i] , f[lt][j] + A[_].a[j][i]);
33
    for(int i = 1;i <= N;i++) f[lt][i] = f[nw][i];
34
  }
35
}
36

37
struct SB { int t , x , y; inline bool operator < (const SB &b) { return t < b.t; } }th[205];
38

39
int main(void){
40
  scanf("%d%d%d%d" , &n , &m , &T , &k);
41
  N = n * 5;
42
  for(int i = 0;i < 30;i++) A[i].clear();
43
  for(int i = 1;i <= n;i++){
44
    scanf("%lld" , &a[i]);
45
    for(int j = 1;j < 5;j++)  A[0].a[ID(i , j)][ID(i , j + 1)] = 0;
46
  }
47
  while(m--){
48
    int u , v , w; scanf("%d%d%d" , &u , &v , &w);
49
    A[0].a[ID(u , w)][v] = max(A[0].a[ID(u , w)][v] , a[v]);
50
  }
51
  for(int i = 1;i <= k;i++) scanf("%d%d%d" , &th[i].t , &th[i].x , &th[i].y);
52
  sort(th + 1 , th + 1 + k);
53
  if(th[k].t != T) th[++k] = (SB){T , 0 , 0};
54
  for(int i = 1;i <= N;i++) f[0][i] = f[1][i] = -inf;
55
  f[0][1] = a[1];
56
  for(int i = 1;i < 30;i++) A[i] = A[i - 1] * A[i - 1];
57
  int lt = 0;
58
  for(int i = 1;i <= k;i++){
59
    mul(th[i].t - lt , (i & 1) , (i & 1 ^ 1));
60
    if(f[th[i].x] >= 0) f[i & 1][th[i].x] += th[i].y;
61
    lt = th[i].t;
62
  }
63
  if(f[k & 1][1] <= 0) puts("-1");
64
  else printf("%lld\n" , f[k & 1][1]);
65
}

T547970#

link

突然发现我好久之前做数学题出的题，当时觉得太简单了，现在看来是太典了。

QWQ_SenLin

结构#

线性#

区间#

背包#