NOIP考点总结之——DP

DP是NOIP考察中较为重要的考点,出现频率也相对较高。不过NOIP中的DP一般不会作为最难的题目的存在,但是其难度也不会很低。近五年主要考察了状压DP,期望DP,树形DP,背包问题变形,序列问题等。其中期望DP是在NOIP2016中首次出现,值得关注。

总概

近五年的NOIP中,DP出现次数也比较高,但大多数的题都是以第二题难度的存在。本文选择了一些近年来的题目来解析。期望,状压,背包,序列问题各选了一道。

NOIP2016 Day1T3 换教室

问题描述

对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。
在可以选择的课程中,有$2n$节课程安排在$n$个时间段上。在第 $i$($1 \leqslant i \leqslant n$)个时间段上,两节内容相同的课程同时在不同的地点进行,其中,牛牛预先被安排在教室$c_i$上课,而另一节课程在教室$d_i$进行。
在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的$n$节安排好的课程。如果学生想更换第$i$节课程的教室,则需要提出申请。若申请通过,学生就可以在第$i$个时间段去教室$d_i$上课,否则仍然在教室$c_i$上课。
由于更换教室的需求太多,申请不一定能获得通过。通过计算,牛牛发现申请更换第$i$节课程的教室时,申请被通过的概率是一个已知的实数$k_i$,并且对于不同课程的申请,被通过的概率是互相独立的。
学校规定,所有的申请只能在学期开始前一次性提交,并且每个人只能选择至多$m$节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室,而不能根据某些课程的申请结果来决定其他课程是否申请;牛牛可以申请自己最希望更换教室的$m$门课程,也可以不用完这$m$个申请的机会,甚至可以一门课程都不申请。
因为不同的课程可能会被安排在不同的教室进行,所以牛牛需要利用课间时间从一间教室赶到另一间教室。
牛牛所在的大学有$v$个教室,有$e$条道路。每条道路连接两间教室,并且是可以双向通行的。由于道路的长度和拥堵程度不同,通过不同的道路耗费的体力可能会有所不同。 当第$i$($1 \leqslant i \leqslant n-1$)节课结束后,牛牛就会从这节课的教室出发,选择一条耗费体力最少的路径前往下一节课的教室。
现在牛牛想知道,申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小,请你帮他求出这个最小值。

输入格式

第一行四个整数$n,m,v,e$。$n$表示这个学期内的时间段的数量;$m$表示牛牛最多可以申请更换多少节课程的教室;$v$表示牛牛学校里教室的数量;$e$表示牛牛的学校里道路的数量。
第二行$n$个正整数,第$i$($1 \leqslant i \leqslant n$)个正整数表示$c_i$,即第$i$个时间段牛牛被安排上课的教室;保证$1 \leqslant c_i \leqslant v$。
第三行$n$个正整数,第$i$($1 \leqslant i \leqslant n$)个正整数表示$d_i$,即第$i$个时间段另一间上同样课程的教室;保证$1 \leqslant d_i \leqslant v$。
第四行$n$个实数,第$i$($1 \leqslant i \leqslant n$)个实数表示$k_i$,即牛牛申请在第$i$个时间段更换教室获得通过的概率。保证$0 \leqslant k_i \leqslant 1$。
接下来$e$行,每行三个正整数$a_j, b_j, w_j$,表示有一条双向道路连接教室$a_j, b_j$,通过这条道路需要耗费的体力值是$w_j$;保证$1 \leqslant a_j, b_j \leqslant v$,$1 \leqslant w_j \leqslant 100$。
保证$1 \leqslant n \leqslant 2000$,$0 \leqslant m \leqslant 2000$,$1 \leqslant v \leqslant 300$,$0 \leqslant e \leqslant 90000$。
保证通过学校里的道路,从任何一间教室出发,都能到达其他所有的教室。
保证输入的实数最多包含$3$位小数。

输出格式

输出一行,包含一个实数,四舍五入精确到小数点后恰好$2$位,表示答案。你的输出必须和标准输出完全一样才算正确。
测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于$4 \times 10^{-3}$。(如果你不知道什么是浮点误差,这段话可以理解为:对于大多数的算法,你可以正常地使用浮点数类型而不用对它进行特殊的处理)

题解

算是概率DP中较为简单的题目。不难想到floyd预处理出任意两点之间的最短路,然后就可以开始考虑DP了。记$dp[i][j][0/1]$表示前$i$个课程中已经申请换了$j$次教室,并且这一次申请/不申请的期望体力值。
对于第三维为$0$的情况,不难得出:
$$dp[i][j][0]=min(dp[i-1][j][1]+p[i-1]·dis[d[i-1]][c[i]]+(1-p[i-1])·dis[c[i-1]][c[i]],dp[i-1][j][0]+dis[c[i-1]][c[i]]);$$
其中前面一个式子表示上一次换了教室,后面表示上一次没换教室。不过对于换了教室的情况,仍然要分为申请成功与失败两种可能。
对于第三维为$1$,形式上相似,不过式子写起来会比较长:
$$dp[i][j][1]=min(p[i]·(dp[i-1][j-1][0]+dis[c[i-1]][d[i]])+(1-p[i])·(dp[i-1][j-1][0]+dis[c[i-1]][c[i]]),p[i]·(dp[i-1][j-1][1]+p[i-1]·dis[d[i-1]][d[i]]+(1-p[i-1])·dis[c[i-1]][d[i]])+(1-p[i])·(dp[i-1][j-1][1]+p[i-1]·dis[d[i-1]][c[i]]+(1-p[i-1])·dis[c[i-1]][c[i]]));$$
于是就解决了。

代码

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=2e3+10;
const int maxm=2e3+10;
const int maxv=3e2+10;
const double INF=1e9;
int c[maxn],d[maxn],dis[maxv][maxv];
double p[maxn],dp[maxn][maxm][2];
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
int main(){
int i,j,k,m,n,v,e;
n=read();m=read();v=read();e=read();
for(i=1;i<=n;i++)c[i]=read();
for(i=1;i<=n;i++)d[i]=read();
for(i=1;i<=n;i++)scanf("%lf",&p[i]);
memset(dis,1,sizeof(dis));
for(i=1;i<=e;i++){
int x,y,z;
x=read();y=read();z=read();
dis[x][y]=dis[y][x]=min(dis[x][y],z);
}
for(i=1;i<=v;i++)dis[i][i]=0;
for(k=1;k<=v;k++)
for(i=1;i<=v;i++)
for(j=1;j<=v;j++)
dis[i][j]=dis[j][i]=min(dis[i][j],dis[i][k]+dis[k][j]);
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
dp[i][j][0]=dp[i][j][1]=INF;
dp[1][0][0]=dp[1][1][1]=0;
for(i=2;i<=n;i++)
for(j=0;j<=min(i,m);j++){
dp[i][j][0]=min(dp[i-1][j][1]+p[i-1]*dis[d[i-1]][c[i]]+
(1-p[i-1])*dis[c[i-1]][c[i]],dp[i-1][j][0]+dis[c[i-1]][c[i]]);
if(j>=1)
dp[i][j][1]=
min(p[i]*(dp[i-1][j-1][0]+dis[c[i-1]][d[i]])+
(1-p[i])*(dp[i-1][j-1][0]+dis[c[i-1]][c[i]]),
p[i]*(dp[i-1][j-1][1]+p[i-1]*dis[d[i-1]][d[i]]+(1-p[i-1])*dis[c[i-1]][d[i]])+
(1-p[i])*(dp[i-1][j-1][1]+p[i-1]*dis[d[i-1]][c[i]]+(1-p[i-1])*dis[c[i-1]][c[i]]));
}
double ans=INF;
for(i=0;i<=m;i++)
ans=min(min(dp[n][i][0],dp[n][i][1]),ans);
printf("%.2lf\n",ans);
return 0;
}

NOIP2016 Day2T3 愤怒的小鸟

问题描述

Kiana最近沉迷于一款神奇的游戏无法自拔。
简单来说,这款游戏是在一个平面上进行的。
有一架弹弓位于$(0,0)$处,每次Kiana可以用它向第一象限发射一只红色的小鸟,小鸟们的飞行轨迹均为形如$y=ax^2+bx$的曲线,其中$a,b$是Kiana指定的参数,且必须满足$a<0$,$a,b$都是实数。
当小鸟落回地面(即$x$轴)时,它就会瞬间消失。
在游戏的某个关卡里,平面的第一象限中有$n$只绿色的小猪,其中第$i$只小猪所在的坐标为$(x_i,y_i)$。
如果某只小鸟的飞行轨迹经过了$(x_i,y_i)$,那么第$i$只小猪就会被消灭掉,同时小鸟将会沿着原先的轨迹继续飞行;
如果一只小鸟的飞行轨迹没有经过$(x_i,y_i)$,那么这只小鸟飞行的全过程就不会对第$i$只小猪产生任何影响。
例如,若两只小猪分别位于$(1,3)$和$(3,3)$,Kiana可以选择发射一只飞行轨迹为$y=?x^2+4x$的小鸟,这样两只小猪就会被这只小鸟一起消灭。
而这个游戏的目的,就是通过发射小鸟消灭所有的小猪。
这款神奇游戏的每个关卡对Kiana来说都很难,所以Kiana还输入了一些神秘的指令,使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。
假设这款游戏一共有$T$个关卡,现在Kiana想知道,对于每一个关卡,至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算,所以希望由你告诉她。

输入格式

第一行包含一个正整数$T$,表示游戏的关卡总数。
下面依次输入这$T$个关卡的信息。每个关卡第一行包含两个非负整数$n,m$,分别表示该关卡中的小猪数量和Kiana输入的神秘指令类型。接下来的$n$行中,第$i$行包含两个正实数$x_i,y_i$,表示第$i$只小猪坐标为$(x_i,y_i)$。数据保证同一个关卡中不存在两只坐标完全相同的小猪。
如果$m=0$,表示 Kiana 输入了一个没有任何作用的指令。
如果$m=1$,则这个关卡将会满足:至多用$\lceil n/3+1 \rceil$只小鸟即可消灭所有小猪。
如果$m=2$,则这个关卡将会满足:一定存在一种最优解,其中有一只小鸟消灭了至少$\lfloor n/3 \rfloor$只小猪。
保证$1 \leqslant n \leqslant 18$,$0 \leqslant m \leqslant 2$,$0<x_i,y_i<10$,输入中的实数均保留到小数点后两位。
上文中,符号$\lceil c \rceil$和$\lfloor c \rfloor$分别表示对$c$向上取整和向下取整,例如:$\lceil2.1\rceil=\lceil2.9\rceil=\lceil3.0\rceil=\lfloor3.0\rfloor=\lfloor3.1\rfloor=\lfloor3.9\rfloor=3$。

输出格式

对每个关卡依次输出一行答案。
输出的每一行包含一个正整数,表示相应的关卡中,消灭所有小猪最少需要的小鸟数量。

题解

这道题同样算是状压DP中较为简单的题了。提前预处理出经过某两点的抛物线能打掉的鸟,并将其状压成一个数。然后就是普通的状压了。不过可以注意,第一只鸟总是要打掉的,因此可以只枚举另一只鸟,这样复杂度可以做到$O(2^n·n)$。

代码

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
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=18;
const double eps=1e-12;
const int INF=1e9;
double x[maxn+5],y[maxn+5];
int dp[(1<<maxn)+10],a[maxn+5][maxn+5];
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
int lowbit(int x){
return x&(-x);
}
bool check(int i,int j,int k){
double x1,x2,y1,y2,z1,z2;
x1=x[i]*x[i];x2=x[j]*x[j];
y1=x[i];y2=x[j];z1=y[i];z2=y[j];
double a=(y2*z1-y1*z2)*1.0/(x1*y2-x2*y1);
double b=(x1*z2-x2*z1)*1.0/(x1*y2-x2*y1);
if(fabs(y2*z1-y1*z2)<eps)return 0;
if((y2*z1-y1*z2)*(x1*y2-x2*y1)>-eps)return 0;
if(fabs(y[k]-a*x[k]*x[k]-b*x[k])<eps)return 1;
else return 0;
}
int main(){
int i,j,k,m,n,T;
#ifndef ONLINE_JUDGE
freopen("angrybirds.in","r",stdin);
freopen("angrybirds.out","w",stdout);
#endif
T=read();
while(T--){
n=read();m=read();
for(i=1;i<=n;i++)
scanf("%lf%lf",&x[i],&y[i]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=(1<<n)-1;
for(i=1;i<=n;i++)a[i][i]=(1<<n)-1-(1<<(i-1));
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
for(k=0;k<n;k++)
if(check(i,j,k+1)){
a[i][j]-=(1<<k);
a[j][i]-=(1<<k);
}
for(i=0;i<(1<<n);i++)dp[i]=INF;
dp[(1<<n)-1]=0;
for(i=(1<<n)-1;i>0;i--){
int pos1,pos2=20;
if(dp[i]==INF)continue;
int tmp=lowbit(i);
pos1=log2(tmp);
for(j=0;j<n;j++){
if((i & (1<<j))){
pos2=j;
dp[i & a[pos1+1][pos2+1]]=min(dp[i & a[pos1+1][pos2+1]],dp[i]+1);
}
}
if(pos2==20)dp[0]=min(dp[0],dp[i]+1);
}
printf("%d\n",dp[0]);
}
return 0;
}

NOIP2015 Day2T2 子串

问题描述

有两个仅包含小写英文字母的字符串$A$和$B$。
现在要从字符串$A$中取出$k$个互不重叠的非空子串,然后把这$k$个子串按照其在字符串$A$中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串$B$相等?
注意:子串取出的位置不同也认为是不同的方案。

输入格式

第一行是三个正整数$n,m,k$,分别表示字符串$A$的长度,字符串$B$的长度,以及问题描述中所提到的$k$,每两个整数之间用一个空格隔开。
第二行包含一个长度为$n$的字符串,表示字符串$A$。
第三行包含一个长度为$m$的字符串,表示字符串$B$。

输出格式

输出共一行,包含一个整数,表示所求方案数。
由于答案可能很大,所以这里要求输出答案对$1000000007$取模的结果。

数据范围

对于100%的数据,$n \leqslant 10^3,k \leqslant m \leqslant 200$。

题解

看完数据范围之后,就不难想到一个DP:设$dp[i][j][k]$表示当前$A$串已选到第$i$位,$B$串已匹配到第$j$位,$A$串已经选择了$k$个子串的方案数。不过这么转移是有问题的,因为这没有考虑两个在$A$串中选择的子串相连的情况。于是我们增加一位$0/1$表示这个子串是否在这个位置结束。转移时要注意思考一下。不过这样写会MLE,我们可以把第一位滚动掉就可以了。

代码

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e3+10;
const int maxm=2e2+10;
const int mod=1e9+7;
int dp[2][maxm][maxm][2];
char a[maxn],b[maxm];
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
int main(){
int i,j,k,m,n,t;
#ifndef ONLINE_JUDGE
freopen("substring.in","r",stdin);
freopen("substring.out","w",stdout);
#endif
n=read();m=read();k=read();
scanf("%s",a+1);
scanf("%s",b+1);
int pos=1;
for(i=1;i<=n;i++){
memset(dp[pos],0,sizeof(dp[pos]));
for(j=1;j<=min(i,m);j++)
for(t=1;t<=k;t++){
if(a[i]==b[j]){
if(j==1 && t==1)dp[pos][j][t][1]=dp[pos][j][t][0]=1;
(dp[pos][j][t][1]+=(dp[pos^1][j-1][t][1]+dp[pos^1][j-1][t-1][0])%mod)%=mod;
(dp[pos][j][t][0]+=(dp[pos^1][j-1][t][1]+dp[pos^1][j-1][t-1][0])%mod)%=mod;
}
(dp[pos][j][t][0]+=dp[pos^1][j][t][0])%=mod;
}
pos^=1;
}
printf("%d\n",dp[pos^1][m][k][0]);
return 0;
}

NOIP2014 Day1T3 飞扬的小鸟

问题描述

Flappy Bird是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度,让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话,便宣告失败。
为了简化问题,我们对游戏规则进行了简化和改编:
游戏界面是一个长为$n$,高为$m$的二维平面,其中有$k$个管道(忽略管道的宽度)。
小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发,到达游戏界面最右边时,游戏完成。
小鸟每个单位时间沿横坐标方向右移的距离为$1$,竖直移动的距离由玩家控制。如果点击屏幕,小鸟就会上升一定高度$X$,每个单位时间可以点击多次,效果叠加;如果不点击屏幕,小鸟就会下降一定高度$Y$。小鸟位于横坐标方向不同位置时,上升的高度$X$和下降的高度$Y$可能互不相同。
小鸟高度等于$0$或者小鸟碰到管道时,游戏失败。小鸟高度为$m$时,无法再上升。
现在,请你判断是否可以完成游戏。如果可以,输出最少点击屏幕数;否则,输出小鸟最多可以通过多少个管道缝隙。

输入格式

第$1$行有$3$个整数$n,m,k$,分别表示游戏界面的长度,高度和水管的数量,每两个整数之间用一个空格隔开;
接下来的$n$行,每行$2$个用一个空格隔开的整数$X$和$Y$,依次表示在横坐标位置$0?n?1$上玩家点击屏幕后,小鸟在下一位置上升的高度$X$,以及在这个位置上玩家不点击屏幕时,小鸟在下一位置下降的高度$Y$。
接下来$k$行,每行$3$个整数$P,L,H$,每两个整数之间用一个空格隔开。每行表示一个管道,其中$P$表示管道的横坐标,$L$表示此管道缝隙的下边沿高度,$H$表示管道缝隙上边沿的高度(输入数据保证$P$各不相同,但不保证按照大小顺序给出)。

输出格式

共两行。
第一行,包含一个整数,如果可以成功完成游戏,则输出$1$,否则输出$0$。
第二行,包含一个整数,如果第一行为$1$,则输出成功完成游戏需要最少点击屏幕数,否则,输出小鸟最多可以通过多少个管道缝隙。

数据范围

对于100%的数据,$5 \leqslant n \leqslant 10000,5 \leqslant m \leqslant 1000$。

题解

这道题是我没有想出正解的题。首先很容易想到一个DP:设$dp[i][j]$表示走到$(i,j)$这个位置的最小点击屏幕的次数。但直接这样转移的话,向上转移就多出来一个$O(m)$的复杂度,无法通过。不过,完全背包给了我们提示,巧妙的转移可以解决这个问题,对于第一次上升,直接转移就好了,否则则利用这一层获得的答案,从$dp[i-1][j-x]$与$dp[i][j-x]$中取较小值进行转移,复杂度即降为$O(nm)$。

代码

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e4+10;
const int maxm=1e3+10;
const int INF=1e9;
int x[maxn],y[maxn],dp[maxn][maxm],flag[maxn];
struct node{
int p,l,h;
};
struct node a[maxn];
bool cmp(node t1,node t2){
return t1.p<t2.p;
}
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
int main(){
int i,j,k,m,n,T;
#ifndef ONLINE_JUDGE
freopen("bird.in","r",stdin);
freopen("bird.out","w",stdout);
#endif
n=read();m=read();k=read();
for(i=1;i<=n;i++){
x[i]=read();
y[i]=read();
}
for(i=1;i<=k;i++){
a[i].p=read();a[i].l=read();a[i].h=read();
}
sort(a+1,a+k+1,cmp);
for(i=1;i<=k;i++)
flag[a[i].p]=i;
int check=0;
memset(dp,127,sizeof(dp));
for(i=0;i<=m;i++)dp[0][i]=0;
for(i=1;i<=n;i++){
for(j=x[i]+1;j<=min(m,2*x[i]);j++)dp[i][j]=min(dp[i][j],dp[i-1][j-x[i]]+1);
for(j=2*x[i]+1;j<=m;j++)
dp[i][j]=min(dp[i][j],min(dp[i][j-x[i]]+1,dp[i-1][j-x[i]]+1));
for(j=m-x[i]+1;j<=m;j++){
dp[i][m]=min(dp[i][m],min(dp[i][j]+1,dp[i-1][j]+1));
}
for(j=1;j<=m-y[i];j++)
dp[i][j]=min(dp[i][j],dp[i-1][j+y[i]]);
if(flag[i]){
for(j=1;j<=a[flag[i]].l;j++)dp[i][j]=INF;
for(j=a[flag[i]].h;j<=m;j++)dp[i][j]=INF;
}
dp[i][0]=INF;
check=0;
for(j=1;j<=m;j++)
if(dp[i][j]<INF)
check=1;
if(!check)break;
}
if(!check)
printf("0\n%d\n",flag[i]-1);
else{
int minans=INF;
for(i=1;i<=m;i++)
minans=min(minans,dp[n][i]);
printf("1\n%d\n",minans);
}
return 0;
}

总结

NOIP中若是出现DP题,一般的难度不会特别大,因此要尽量争取考场上解决。即使没有解决,也应尽量拿下最高的部分分。考场上一定要注意,若是在写DP题时,一定要先把状态转移方程认真推一下,写下来,再来实现。
常见的需要想到DP的题目类型:

  • 求方案数并明确说了取模;
  • 求最优的方案的最小步数/最大得分等;
  • 求期望的肯定是DP;
  • 树上的一些统计可以考虑树形DP;
  • 其中某个数范围在$20$以内要想到状压;
  • 各个数位上的要求之类的想到数位DP;