\(\qquad\!\!\)除了基础动态规划中的三种动态规划以外，还有一些比较难的动态规划：
- 1、树形dp：
- (1)、基础树形dp
- (2)、递归前转移树形dp
- (3)、递归后转移树形dp
- (4)、树上01背包
- (5)、树上分组背包
- (6)、基础换根dp
- (7)、进阶换根dp
- (8)、基环树之树形dp+环形dp
- (9)、基环树之开环直接树形dp
- 2、DAG上的dp（拓扑排序）：
\(\qquad\!\!\)就是拓扑排序。
\(\qquad\!\!\)例题：
\(\qquad\!\!\)P4017
最大食物链计数：
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
| #include<bits/stdc++.h>
#define in inline
#define re register
const int N=5010;
const int M=500010;
const int P=80112002;
using namespace std;
int n,m;
int cnt,head[N];
struct edge
{
int to,nxt;
};
edge e[M];
int rd[N],cd[N];
int f[N];
int ans;
in int qread()
{
int x=0,y=1;
int ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
in void qwrite(re int x)
{
if(x<0)
{
putchar('-');
qwrite(-x);
}
else
{
if(x>9)
{
qwrite(x/10);
}
putchar(x%10+'0');
}
return ;
}
in void mr(re int u,re int v)
{
cd[u]++;
rd[v]++;
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
return ;
}
in void tppx()
{
queue<int> q;
for(re int i=1;i<=n;i++)
{
if(!rd[i]&&cd[i])
{
q.push(i);
f[i]=1;
}
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(re int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
f[v]=(f[u]+f[v])%P;
rd[v]--;
if(!rd[v]&&!cd[v])
{
ans=(ans+f[v])%P;
}
if(!rd[v]&&cd[v])
{
q.push(v);
}
}
}
return;
}
int main()
{
n=qread();
m=qread();
for(re int i=1;i<=m;i++)
{
int u=qread();
int v=qread();
mr(u,v);
}
tppx();
qwrite(ans?ans:1);
putchar('\n');
return 0;
}
|
\(\qquad\!\!\)在形成了环形以后，从一段开始再从另一端结束的dp已经不能满足所有条件。
\(\qquad\!\!\)我们考虑上述的这种情况即为断开了环形的一条边。这样在处理时，我们先假设这条边是断开的，统计一下符合条件的个数，再强行把这条边连上，并统计符合条件的断开边后统计不到的答案。这样，所有的答案就没有遗漏。
\(\qquad\!\!\)例题：
\(\qquad\!\!\)P6064 [USACO05JAN]Naptime
G：
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
| #include<bits/stdc++.h>
#define in inline
#define re register
const int N=3850;
using namespace std;
int n,m;
int val[N];
int f[N][N][2];
int ans;
in int qread()
{
int x=0,y=1;
int ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
in void qwrite(re int x)
{
if(x<0)
{
putchar('-');
qwrite(-x);
}
else
{
if(x>9)
{
qwrite(x/10);
}
putchar(x%10+'0');
}
return ;
}
int main()
{
n=qread();
m=qread();
for(re int i=1;i<=n;i++)
{
val[i]=qread();
}
memset(f,-0x3f,sizeof(f));
f[1][0][0]=0;
f[1][1][1]=0;
for(re int i=2;i<=n;i++)
{
for(re int j=1;j<=m;j++)
{
f[i][j][0]=max(f[i-1][j][1],f[i-1][j][0]);
if(f[i-1][j-1][1]<0)
{
f[i][j][1]=max(f[i-1][j-1][0],0);
}
else
{
f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j-1][1]+val[i]);
}
}
}
ans=max(f[n][m][0],f[n][m][1]);
memset(f,-0x3f,sizeof(f));
f[1][1][1]=val[1];
for(re int i=2;i<=n;i++)
{
for(re int j=1;j<=m;j++)
{
f[i][j][0]=max(f[i-1][j][1],f[i-1][j][0]);
if(f[i-1][j-1][1]<0)
{
f[i][j][1]=max(f[i-1][j-1][0],0);
}
else
{
f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j-1][1]+val[i]);
}
}
}
ans=max(ans,f[n][m][1]);
qwrite(ans);
putchar('\n');
return 0;
}
|
\(\qquad\!\!\)区间dp
是通过两个相邻区间的最优决策从而推出整体区间的最优决策的一类dp问题，以时间复杂度较大（常为
\(O(n^3)\)）作为特点。一部分具有相关性质的题目可以利用四边形不等式优化到
\(O(n^2)\)。
\(\qquad\!\!\)例题：
\(\qquad\!\!\)P1880
[NOI1995]石子合并：
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
| #include<bits/stdc++.h>
#define in inline
#define re register
const int N=210;
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
int a[N],pre[N];
int f[N][N][2];
int ans1,ans2=inf;
in int qread()
{
int x=0,y=1;
int ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
in void qwrite(re int x)
{
if(x<0)
{
putchar('-');
qwrite(-x);
}
else
{
if(x>9)
{
qwrite(x/10);
}
putchar(x%10+'0');
}
return ;
}
int main()
{
n=qread();
for(re int i=1;i<=n;i++)
{
a[i]=qread();
if(i^n)
{
a[n+i]=a[i];
}
}
m=(n<<1)-1;
for(re int i=1;i<=m;i++)
{
pre[i]=pre[i-1]+a[i];
if(i^m)
{
f[i][i+1][0]=a[i]+a[i+1];
f[i][i+1][1]=a[i]+a[i+1];
}
}
for(re int l=2;l<n;l++)
{
for(re int i=1,j=i+l;i<=m&&j<=m;i++,j=i+l)
{
f[i][j][1]=inf;
for(re int k=i;k<j;k++)
{
f[i][j][0]=max(f[i][j][0],f[i][k][0]+f[k+1][j][0]+pre[j]-pre[i-1]);
f[i][j][1]=min(f[i][j][1],f[i][k][1]+f[k+1][j][1]+pre[j]-pre[i-1]);
}
}
}
for(re int i=1;i<=n;i++)
{
ans1=max(ans1,f[i][i+n-1][0]);
ans2=min(ans2,f[i][i+n-1][1]);
}
qwrite(ans2);
putchar('\n');
qwrite(ans1);
putchar('\n');
return 0;
}
|
\(\qquad\!\!\)状压dp
通常利用一个数字表示一种状态，利用位运算进行状态的转移。一般状压的题目的数据范围都会很小（\(n=15-25\)），所以一旦碰到了这样的小数据范围的话一定要思考一下能不能
状压dp。
\(\qquad\!\!\)例题：
\(\qquad\!\!\)P1896 [SCOI2005]互不侵犯
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
| #include<bits/stdc++.h>
#define in inline
#define re register
#define int long long
using namespace std;
int n,k;
int f[10][(1<<9)+(1<<8)][100];
int ans,temp1,temp2;
in int qread()
{
int x=0,y=1;
int ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
in void qwrite(re int x)
{
if(x<0)
{
putchar('-');
qwrite(-x);
}
else
{
if(x>9)
{
qwrite(x/10);
}
putchar(x%10+'0');
}
return ;
}
in int cs(int x)
{
int y=0;
while(x)
{
if(x&1)
{
y++;
}
x>>=1;
}
return y;
}
in bool pd1(int x,int y)
{
if(y<=k&&(!(x&(x<<1)))&&(!(x&(x>>1))))
{
return 1;
}
return 0;
}
in bool pd2(int x,int y,int z)
{
if(pd1(x,z)&&(!(x&(y<<1)))&&(!(x&y))&&(!(x&(y>>1))))
{
return 1;
}
return 0;
}
signed main()
{
n=qread();
k=qread();
int temp_=(1<<n)-1;
for(re int i=0;i<=temp_;i++)
{
int temp4=cs(i);
if(pd1(i,temp4))
{
f[1][i][temp4]=1;
}
if(n==1)
{
ans+=f[1][i][k];
}
}
if(n==1)
{
qwrite(ans);
putchar('\n');
return 0;
}
for(re int i=2;i<=n;i++)
{
for(re int v=0;v<=temp_;v++)
{
temp2=cs(v);
if(pd1(v,temp2))
{
for(re int u=0;u<=temp_;u++)
{
temp1=cs(u);
if(pd2(u,v,temp1))
{
int temp3=k-temp2;
for(re int j=temp1;j<=temp3;j++)
{
f[i][v][j+temp2]+=f[i-1][u][j];
}
}
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=temp_;j++)
{
ans+=f[i][j][k];
}
}
qwrite(ans);
putchar('\n');
return 0;
}
|
\(\qquad\!\!\)数位dp
一般解决的是一类数字问题：从 \(l\) 到
\(r\) 有多少个数符合某个性质，其中
\(l\) 和 \(r\) 都是很大的数，从 \(l\) 循环到 \(r\) 显然会
TLE。这样，我们就可以利用在每个数位上进行统计的方法进行
数位dp，一般来说，数位dp 由 dp、拆数、容斥三部分组成。
\(\qquad\!\!\)例题：
\(\qquad\!\!\)P2657 [SCOI2009] windy
数：
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
| #include<bits/stdc++.h>
#define in inline
#define re register
using namespace std;
int A,B;
int f[20][20],a[20];
in int qread()
{
int x=0,f=1;
int c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
in void qwrite(int x)
{
if(x<0)
{
putchar('-');
x=-x;
qwrite(x);
}
else
{
if(x>9)
{
qwrite(x/10);
}
putchar(x%10+'0');
}
}
in int js(int x)
{
memset(a,0,sizeof(a));
int l=0,ans=0;
while(x)
{
l++;
a[l]=x%10;
x/=10;
}
for(re int i=1;i<l;i++)
{
for(re int j=1;j<=9;j++)
{
ans+=f[i][j];
}
}
for(re int i=1;i<a[l];i++)
{
ans+=f[l][i];
}
for(re int i=l-1;i>=1;i--)
{
for(re int j=0;j<a[i];j++)
{
if(abs(a[i+1]-j)<2)
{
continue;
}
ans+=f[i][j];
}
if(abs(a[i+1]-a[i])<2)
{
break;
}
}
return ans;
}
int main()
{
for(re int i=0;i<=9;i++)
{
f[1][i]=1;
}
for(re int i=2;i<=10;i++)
{
for(re int j=0;j<=9;j++)
{
for(re int k=0;k<=9;k++)
{
if(abs(k-j)<2)
{
continue;
}
f[i][j]+=f[i-1][k];
}
}
}
A=qread();
B=qread();
qwrite(js(B+1)-js(A));
putchar('\n');
return 0;
}
|
\(\qquad\!\!\)期望dp 或者叫 概率dp
是一类有关数学上的概率和期望的dp问题。一般由于期望的可传递性而需要计算较大范围下的期望。其实这种算法虽然叫做dp，但是其实一般并不需要进行最优决策，只是由于其需要计算的东西满足无后效性而可以利用dp的方式来做。
\(\qquad\!\!\)例题：
\(\qquad\!\!\)CF235B Let's Play
Osu!：
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
| #include<bits/stdc++.h>
#define in inline
#define re register
using namespace std;
int n;
double x,x1,ans;
in int qread()
{
int x=0,y=1;
int ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
int main()
{
n=qread();
while(n--)
{
scanf("%lf",&x);
ans+=x*(2*x1+1);
x1=x*(x1+1);
}
printf("%.10lf\n",ans);
return 0;
}
|
- 8、dp计数
- 9、dp优化：
- (1).斜率优化
- (2).四边形不等式优化
- (3).数据结构优化：
- ①.单调栈/单调队列优化
- ②.树状数组优化
- ③.线段树优化
- ④.矩阵快速幂优化