template-DP

Posted on Edited on

单调队列

O(n)求 最大值-最小值 <= 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
int getNum(int target)
{
    if(nums.empty())
        return 0;
    deque<int> qmin;    //保存窗口内的最小值，递增  front保存最小的元素位置
    deque<int> qmax;    //保存窗口内的最大值，递减  front保存最大的元素位置
    int i = 0, j = 0;   //nums[i..j]表示数组的范围
    int res = 0;        //表示满足条件的子数组数量
    //依次找到以nums[0],nums[1]...nums[N - 1]作为第一元素的子数组中满足条件的数量有多少个，累加
    while(i < nums.size())
    {
        while(j < nums.size())   // j向右拓展，直到不满足条件
        {
            while(!qmin.empty() && nums[qmin.back()] >= nums[j]) // 更新qmin中最小值的index
                qmin.pop_back();
            qmin.push_back(j);
            while(!qmax.empty() && nums[qmax.back()] <= nums[j]) // 更新qmax中最大值的index
                qmax.pop_back();
            qmax.push_back(j);
            if(nums[qmax.front()] - nums[qmin.front()] > target) //如果出现不满足条件的，那么包含以nums[i]起始的窗口的所有子数组都不满足条件
                break;
            j++;
        }
        if(qmin.front() == i)  // 如果窗口为 0 ，直接弹出
            qmin.pop_front();
        if(qmax.front() == i)  // 如果窗口为 0 ，直接弹出
            qmax.pop_front();
        res += j - i;          //如果nums[i..j]满足条件，则其子数组都满足条件， 一共 (j - i)个子数组
        i++;                   //继续寻找以nums[i]为起始点的子数组
    }
    return res;
}

单调栈

求全为1的最大子矩形面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int cal() {
    ans = 0;
    stack<int> st;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= m + 1; j++) {
            if (st.empty() || s[j] >= s[st.top()]) {
                st.push(j);
            } else {
                int top;
                while (!st.empty() && s[j] < s[st.top()]) {
                    top = st.top();
                    st.pop();
                    int tmp = (j - top) * s[top];
                    ans = max(ans, tmp);
                }
                st.push(top);
                s[top] = s[j];
            }
        }
    }
    return ans;
}

基础

最长上升子序列

nlogn做法

二分

\(f[i]\)表示长度为\(i\)的最长上升子序列中, 最小的末尾数值. \(siz\)为最长上升子序列长度.

1
2
3
4
5
6
7
8
9
f[1] = raw[1];
int siz = 0;
for(int i = 2;i <= n;i++){
    if(f[siz] < raw[i])f[++siz] = raw[i];
    else{
        int idx = lower_bound(f+1,f+siz+1,raw[i]) - f;
        f[idx] = min(f[idx],raw[i]);
    }
}

悬线法

同样用来求最大子矩形问题, 时间复杂度\(O(nm)\)

设\(l[x][y],r[x][y],u[x][y]\)为点\((x,y)\)可向左/右/上移动的最大距离. (其中向上扩展的最大距离即为"悬线"长度)

求出以上距离后, 再令\(L[x][y],R[x][y]\)为\((x,y)\)的悬线可以向左/右扩展的最大距离. 有: \[ L[x][y] = \begin{cases} \min(l[x-1][y],L[x][y]) & (x-1,y)合法\\ l[x][y] & (x-1,y)非法 \end{cases} \] 再统计\(\max(u[x][y] \cdot (L[x][y] + R[x][y] - 1))\)即为答案.

状压dp

TSP问题

(变体):给出一个带权完全无向图, 求恰好经过每一点的最短简单路径

1
2
3
4
5
6
7
8
9
10
11
12
int f[1<<20][20];
memset(f,0x3f3f3f3f,sizeof(f));
for(int i = 1;i <= k;i++)f[1<<(i-1)][i] = 1;
for(int S = 1;S < (1<<k);S++){
    for(int i = 1;i <= k;i++)if(S&(1<<(i-1))){
        for(int j = 1;j <= k;j++)if(j != i and S&(1<<(j-1))){
            f[S][i] = min(f[S][i],f[S ^ (1<<(i-1))][j] + dis[i][j]);
        }
    }
}
ll ans = INF;
for(int i = 1;i <= k;i++)ans = min(ans,f[(1<<k)-1][i]);

求无向图简单环个数

设\(f[S][i]\)表示状态为\(S\), 终点是\((1<<i)\), 起点是\(lowbit(S)\)的链的个数:

由于是无向图, 需要减去边的个数后除以2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int ans = 0;
for(int i = 0;i < n;i++)f[(1<<i)][i] = 1;
for(int S = 1;S < (1<<n);S++){
	for(int u = 0;u < n;u++)if((S >> u) & 1){
		for(int v:G[u]){
			int l = lowbit(S);
			if((1<<v) < l)continue;
			if((1<<v) > l and !((S >> v) & 1)){
				f[S | (1<<v)][v] += f[S][u];
			}
			else if((1<<v) == l)ans += f[S][u];
		}
	}
}
ans -= m;
cout << ans / 2;

数位dp

感觉这个神秘板子部分就数位dp有用啊?

例题1

定义一个正整数的价值是把这个数的十进制写出来之后，最长的等差子串的长度。

求\([l,r]\)范围内数字价值的总和。

板子来源

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m,len,a[20];
ll l,r,dp[20][15][25][25][20];
ll dfs(int pos,int pre,ll st,ll sum,int d,int lead,int limit){
	//pos搜到的位置
	//pre前一位数
	//st当前公差最大差值
	//sum整个数字的最大价值
	//d公差
	//lead判断是否有前导0
	//limit判断是否有最高位限制
	if(pos>len) return sum;//dp结束 
	//记录状态（计划搜索）
	//注意d有负数，最小可以到-9，所以记录时数组下标是d+10 
	if((dp[pos][pre][st][sum][d+10]!=-1&&(!limit)&&(!lead))) return dp[pos][pre][st][sum][d+10]; 
	ll ret=0;
	int res=limit?a[len-pos+1]:9;//最高位最大值 
	for(int i=0;i<=res;i++){
		//有前导0且这位也是前导0，一切不变只有位数变化 
		if((!i)&&lead) ret+=dfs(pos+1,0,0,0,-38,1,limit&&(i==res));
		//有前导0但这位不是前导0（这位是数字的最高位）开始有前一位，一个数形成等差数列 
		else if(i&&lead) ret+=dfs(pos+1,i,1,1,-38,0,limit&&(i==res));
		//之前刚搜到1位还没有共差，两位数形成等差数列，记录共差 
		else if(d<-9) ret+=dfs(pos+1,i,2ll,2ll,i-pre,0,limit&&(i==res));
		//搜到2位以后，共差若与前两位相同当前等差数列长度增加，若公差变化则更新整个数字的最大价值，等差数列长度又变为2 
		else if(d>=-9) ret+=dfs(pos+1,i,(i-pre==d)?st+1:2,max(sum,(i-pre==d)?st+1:2),(i-pre==d)?d:i-pre,0,limit&&(i==res));
	}
	//没有前导0和最高限制时可以直接记录当前dp值以便下次搜到同样的情况可以直接使用。 
	return (!limit&&!lead)?dp[pos][pre][st][sum][d+10]=ret:ret;
}
ll part(ll x){
	len=0;
	while(x) a[++len]=x%10,x/=10;
	memset(dp,-1,sizeof dp);
	return dfs(1,0,0,0,-38,1,1);//-38是随便赋的其实赋成-10就行了…… 
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld%lld",&l,&r);
		//l是0的时候要特别注意！
	    printf("%lld\n",l?(part(r)-part(l-1)):(part(r)-part(l)+1));
	}
	return 0;
}

例题2

求不含前导零且相邻两个数字之差至少为\(2\)的正整数

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[15][15],ans;//dp[i][j]表示搜到第i位，前一位是j，的！limit方案totnum；
int a[15],len;
long long L,R;
ll dfs(int pos,int pre,int st,int limit)//pos当前位置,pre前一位数,st判断前面是否全是0,limit最高位限制 
{
	if(pos>len) return 1;//搜完了 
	if(!limit&&dp[pos][pre]!=-1) return dp[pos][pre];//没有最高位限制，已经搜过了
	ll ret=0;
	int res=limit?a[len-pos+1]:9;//当前位最大数字 
	for(int i=0;i<=res;i++)//从0枚举到最大数字 
	{
		if(abs(i-pre)<2) continue;//不符合题意，继续 
		if(st&&i==0) ret+=dfs(pos+1,-2,1,limit&&i==res);//如果有前导0，下一位随意 
		else ret+=dfs(pos+1,i,0,limit&&i==res);//如果没有前导0，继续按部就班地搜 
	}
	if(!limit&&!st) dp[pos][pre]=ret;//没有最高位限制且没有前导0时记录结果 
	return ret;
}
void part(ll x)
{
	len=0;
	while(x) a[++len]=x%10,x/=10;
	memset(dp,-1,sizeof dp);
	ans=dfs(1,-2,1,1);
}
int main()
{
    scanf("%lld%lld",&L,&R);
    part(L-1);ll minn=ans;
	part(R);  ll maxx=ans;
	printf("%lld",maxx-minn);
	return 0;
}

优化

斜率优化

维护\(y_i = k_i x + b_i\)的最小值. update(\(k,b\))需要保证斜率\(k\)单调递减. 其他情况自己推一下即可.

原理如下图. 插入时, line存构成当前下凸壳的直线, point[i]代表直线line[i]和line[i-1]的交点横坐标. 新加入一条直线(\(l_3)\)时, 设\(l_3\)和\(l_2\)交于\(B\), \(l_2\)和\(l_1\)交于\(A\). 若\(B.x < A.x\)则显然\(l_2\)不再组成下凸壳, 将其删去. 使用单调栈维护这一过程即可. 查询时在point上二分即可找到对应直线.

image-20220824102152715

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
const ll INF = 1e18;//
int sgn(int x){return (x > 0) - (x < 0);}
struct Frac{
	int u,d;
	Frac(int a,int b){
		ll sg = sgn(a) * sgn(b);
		if(a < 0)a = -a;
		if(b < 0)b = -b;
		//ll g = __gcd(a,b);
		//if(g > 1)a /= g,b /= g;
		u = sg * a,d = b;
	}
	bool operator < (const Frac & x) const{
		return (__int128)u * x.d < (__int128)d * x.u; 
	}
	bool operator <= (const Frac & x) const{
		return (__int128)u * x.d <= (__int128)d * x.u; 
	}
	bool operator == (const Frac & x) const{
		return u == x.u and d == x.d;
	}
};
struct Line{
	int k,b;
	Line(int k = 0,int b = 0):k(k),b(b){}
	int operator () (int x){
		return k * x + b;
	}
	Frac operator ^ (const Line & B)const{//return intersection.x
		return {B.b - b,k - B.k};
	}
};
vector<Line>line;
vector<Frac>inter;//intersector.x
void update(int k,int b){
	Frac x = {-INF,1};
	Line cur = Line(k,b);
	while(line.size() and (x = line.back() ^ cur) <= inter.back()){
		line.pop_back(),inter.pop_back();
	}
	line.push_back(cur);
	inter.push_back(x);
}
int query(int x){
	Frac v = {x,1};
	int idx = upper_bound(ALL(inter),v) - inter.begin() - 1;
	return line[idx](x);
}