dp基础√
1.重叠子问题
2.能从小问题推到大问题
Dp:
设计状态+状态转移
状态:
1.状态表示: 是对当前子问题的解的局面集合的一种（充分的）描述。(尽量简洁qwq)
◦ 对于状态的表示，要满足三条性质
◦ 1：具有最优化子结构：即问题的最优解能有效地从问题的子问题的最优解构造而来。
◦ 2：能够全面的描述一个局面。一个局面有一个答案，而这个局面是需要一些参数来描述的。
◦ 3：同时具有简洁性：尽可能的简化状态的表示，以获得更优的时间复杂度。
◦ 设计状态的关键就是 充分描述，尽量简洁。
2.最优化值：则是对应的状态集合下的最优化信息（方案值），我们最终能通过其直接或间接得到答案。
3.状态转移:
- 由于具有最优化子结构（在最优化问题中），所以求当前状态的最优值可以通过其他的（较小的问题）状态的最优值加以变化而求出。所以，当一个状态的所有子结构都已经被计算之后，我们就可以通过一个过程计算出他的最优值。这个过程就是状态的转移。
- 注意：状态的转移需要满足要考虑到所有可能性。
以上全都在凑字数↑
怎么计算dp时间复杂度:一般的简单dp时间复杂度=状态数*状态转移复杂度;
Dp两种优化方法:
1.减少状态维数;2.加速状态转移,例如数据结构优化或者分析性质
下面看题：
最长上升子序列：
dp[i]表示以i结尾的最长上升子序列，dp[i]=max(dp[j])j∈1~i-1，a[j]<a[i];
◦ 设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
◦ 有一个数字串：312，当N=3，K=1时会有以下两种分法：
◦ 1) 3*12=36
◦ 2) 31*2=62
◦ 这时，符合题目要求的结果是：31*2=62
◦ 现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
◦ N，K（6≤N≤80，1≤K≤50）
SOTUTION：
◦ 用 f[i][a] 表示前 i 位数包含 a 个乘号所能达到的最大乘积，我们只需要枚举上一个乘号所在的位置即可。
◦ 将 j 从 a 到 i - 1 进行一次枚举，表示前 j 位中含有 a-1 个乘号，且最后一个乘号的位置在 j 处。那么当最后一个乘号在 j 处时最大值为前 j 位中含有 a - 1 个乘号的最大值乘上 j 处之后到i的数字。
◦ 因此得出了状态转移方程 f[i][a] = max(f[i][a] , f[j][a-1] * cut(j + 1,i))
——（cut(b + 1,i) 表示 b + 1 到 i 位数字）
◦ 然后再写个高精度即可。
（然后又因为要写高精放弃了..）
N个装在手机上的挂饰。挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上，要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有1个。此外，每个挂件有一个安装时会获得的喜悦值，用一个整数来表示，可能为负。
想要选出一些挂饰挂在一起，最大化所有挂饰的喜悦值之和。
1<=N<=2000
0<=Ai<=N(1<=i<=N)表示挂勾的数量
-10^6<=Bi<=10^6(1<=i<=N)表示喜悦值。
SOLUTION：
先按挂钩数从大到小排序:
然后设dp[i][j]前i个挂饰，剩余j个挂钩的最大喜悦值是多少即可。
初始化dp数组非常非常小;
初始状态dp[0][1]=0;也就是啥挂饰也没有，有一个挂钩（手机自带）的喜悦值是0；
转移：dp[i][j]=max(dp[i-1][j],dp[i-1][max(j-a[i],0)+1]+b[i]);
关于我们取第i个物品的值：
首先显然由i-1转移过来，然后因为选择了第i个挂饰，且选择后挂钩为j个，所以在第i-1个挂饰时，挂钩数为j-a[i]（第i个物品挂钩数）+1（因为自身挂的话还要用一个挂钩）
对于为啥要和0取max，当j-a[i]为负数时，我们需要把之前一切都推翻，只留第i个挂饰，那么挂钩数是手机本来就有的1个挂钩；
最后答案：在dp[n][0~n]中取max；
注意dp[i][0]不能转移。
CODE：
#include
using namespace std;
inline int read(){
int ans=;
char last=' ',ch=getchar();
while(ch>''||ch<'') last=ch,ch=getchar();
while(ch>=''&&ch<='') ans=(ans<<)+(ans<<)+ch-'',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
int n,ans;
struct node{
int a,b;
}g[];
bool cmp(node x,node y){
if(x.a==y.a) return x.b>y.b;
return x.a>y.a;
}
int dp[][];
int main(){
n=read();
for(int i=;i<=n;i++){
g[i].a=read();
g[i].b=read();
}
sort(g+,g+n+,cmp);
memset(dp,-,sizeof(dp));
dp[][]=;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
dp[i][j]=max(dp[i-][j],dp[i-][max(j-g[i].a,)+]+g[i].b);
}
}
for(int i=;i<=n;i++)
ans=max(ans,dp[n][i]);
printf("%d",ans);
return ;
}
LIS问题
luogu p1233木棍加工;
一堆木头棍子共有n根，每根棍子的长度和宽度都是已知的。棍子可以被一台机器一个接一个地加工。机器处理一根棍子之前需要准备时间。准备时间是这样定义的：
第一根棍子的准备时间为1分钟；
如果刚处理完长度为L，宽度为W的棍子，那么如果下一个棍子长度为Li，宽度为Wi，并且满足L>＝Li，W>＝Wi，这个棍子就不需要准备时间，否则需要1分钟的准备时间；
计算处理完n根棍子所需要的最短准备时间。比如，你有5根棍子，长度和宽度分别为(4, 9)，(5, 2)，(2, 1)，(3, 5)，(1, 4)，最短准备时间为2（按(4, 9)、(3, 5)、(1, 4)、(5, 2)、(2, 1)的次序进行加工）。
N<=5000
SOLUTION:
把l从大到小排序如果l相同按w从大到小排序；然后求w的最少不上升子序列覆盖数；
一个定理：dilworth定理（qyf好像提过）
在本题中;
不上升子序列覆盖数=最长上升子序列长度;
其实就和导弹拦截差不多了qwq；
#include
using namespace std;
inline int read(){
int ans=;
char last=' ',ch=getchar();
while(ch>''||ch<'') last=ch,ch=getchar();
while(ch>=''&&ch<='') ans=(ans<<)+(ans<<)+ch-'',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
int n,ans;
struct node{
int a,b;
}g[];
bool cmp(node x,node y){
if(x.a==y.a) return x.b>y.b;
return x.a>y.a;
}
int f[];
int main(){
n=read();
for(int i=;i<=n;i++){
g[i].a=read();
g[i].b=read();
}
sort(g+,g+n+,cmp);
f[]=;
for(int i=;i<=n;i++){
for(int j=;j<i;j++){
if(g[j].b<g[i].b) f[i]=max(f[i],f[j]+);
}
ans=max(ans,f[i]);
}
printf("%d",ans);
return ;
}
luogu p1091 合唱队形
N 位同学站成一排，音乐老师要请其中的( N−K )位同学出列，使得剩下的 K 位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为 1,2,…，他们的身高分别为 T_1,T_2,…,T_K
则他们的身高满足 T1
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
n<=100000
SOLUTION：
我们设f[i]表示以i结尾的最长上升子序列长度。
我们设g[i]表示以i开头的最长下降子序列长度。
然后我们枚举哪一个为中心的最高点，f[i]+g[i]-1取最大值即可。
#include
using namespace std;
inline int read(){
int ans=;
char last=' ',ch=getchar();
while(ch>''||ch<'') last=ch,ch=getchar();
while(ch>=''&&ch<='') ans=(ans<<)+(ans<<)+ch-'',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
int n,ans;
int a[];
int f[],g[];
int main(){
n=read();
for(int i=;i<=n;i++)
a[i]=read(),f[i]=g[i]=;
for(int i=;i<=n;i++)
for(int j=;j
for(int j=n;j>i;j--)
if(a[j]<a[i]) g[i]=max(g[i],g[j]+);
for(int i=;i<=n;i++)
ans=max(ans,f\[i\]+g\[i\]-);
printf("%d",n-ans);
return ; }
求最长上升子序列的另外两种方法：
1.比较有脑难以理解的方法;
神仙辅助数组：我们考虑新定义一个数组h[k]表示dp[j]=k的所有状态中，a[j]的值，最小的一个（显然我们为了以后好更新需要满足最小这个条件），然后一波玄学证明，我们可以尝试证明h[k]的答案是递增的（即h[k]<h[k+1]）：
假设不是递增的:那么h[k]>=h[k+1]，
那么我们显然可以在h[k+1]中找到a[j]更小的j,使得dp[j]=k，矛盾，因此一定是递增的；
然后这个样子我们对于一个a[i]就可以找到,最大的k，满足h[k]是小于a[i]的，然后f[i]=k+1。 找的过程是可以二分加速的。
然后同时在维护出h数组即可。
2.无脑的数据结构优化：
我们把a[j]看成坐标，dp[j]看成权值，这就是每次求坐标小于等于某个值的权值最大值，然后每算完一个单点修改即可。（乱死了qwq）
LCS问题
给定两个字符串S和T，长度分别为n和m，求解这两个字符串的最长公共子序列（Longest Common Sequence）。
比如字符串S：BDCABA；字符串T：ABCBDAB
则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA。
n,m<=1000
设dp[i][j]表示s串的第i个前缀 和t串的第j个前缀的最长公共子序列；
分情况：
如果S[i]==T[j]，dp[i][j]=dp[i-1][j-1]+1;
如果S[i]!=T[j]，dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
最后答案就是dp[n][m]；
#include
using namespace std;
inline int read(){
int ans=;
char last=' ',ch=getchar();
while(ch>''||ch<'') last=ch,ch=getchar();
while(ch>=''&&ch<='') ans=(ans<<)+(ans<<)+ch-'',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
int n,ans;
int x[],y[];
int dp[][];
int main(){
n=read();
for(int i=;i<=n;i++)
x[i]=read();
for(int i=;i<=n;i++)
y[i]=read();
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(x[i]==y[j]) dp[i][j]=dp[i-][j-]+;
else dp[i][j]=max(dp[i-][j],dp[i][j-]);
ans=max(ans,dp[i][j]);
}
}
printf("%d",ans);
return ;
}
50pts Code
被gu掉的正解：
因为这个题是1~n的一个全排列，所以我们可以保证每个数字只出现一次，并且两个排列中所有的数字都是相同的；
那么影响这两个排列的公共子序列的就是这两个排列的顺序，顺序不同，答案不同。因此我们将第一个序列的数字在第二个序列中表示出来，然后对这个序列求一个LIS，LIS的长度就是最终长度；
值得注意的是，因为数据范围很大，我们要对LIS采取优化，可以看上面另外两种求LIS的方法中的第一种，代码与上面思路不同的是，我们找的是第一个>=当前数的而并不是<;
#include
using namespace std;
inline int read(){
int ans=;
char last=' ',ch=getchar();
while(ch>''||ch<'') last=ch,ch=getchar();
while(ch>=''&&ch<='') ans=(ans<<)+(ans<<)+ch-'',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
int n,ans;
int x[],y;
int a[];
int f[];
int main(){
n=read();
for(int i=;i<=n;i++)
x[i]=read(),a[x[i]]=i;
int len=;
for(int i=,now;i<=n;i++) {
y=read();
now=a[y];
if(now>f[len]) f[++len]=now;
else {
int j=lower_bound(f+,f++len,now)-f;
f[j]=now;
}
}
cout<<len<<endl;
return ;
}
给两个序列A长度为n和B长度为m，求最长的公共子序列，还要保证这个序列是上升的。
O(n^4) dp[i][j]表示A串的第i个位置和B串第j个位置的最长公共上升子序列的长度；
那么O(n^4)算法，枚举每个k<i,l<j，计算dp值，然后进行转移；
O(n^3) 每次增加的实际上只有
黄色线部分增加了，因此我们可以枚举k<i,计算dp[k][j]，取max；
O(n^2)定义数组f[j]=max{dp[1~i-1][j]};
然后dp[i][j]=max{f[k] | k<j && B[k]<A[i]}，
然后尝试O(n^2)维护辅助数组f[j];f[j]实际在b串作用；
a[i]>b[j]：因为相等才更新dp值，因此a[i]>b[j]也就保证了a[x]>b[j]，其中b[x]==a[i];
#include
using namespace std;
inline int read(){
int ans=;
char last=' ',ch=getchar();
while(ch>''||ch<'') last=ch,ch=getchar();
while(ch>=''&&ch<='') ans=(ans<<)+(ans<<)+ch-'',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
int n,m;
int ans;
int s[],t[];
int dp[][];
int f[];
int main(){
n=read();
for(int i=;i<=n;i++)
s[i]=read();
m=read();
for(int i=;i<=m;i++)
t[i]=read();
for(int i=;i<=n;i++){
int tmp=;
for(int j=;j<=m;j++){
if(s[i]==t[j]){
dp[i][j]=tmp+;
f\[j\]=max(f\[j\],tmp+);
}
else if(s\[i\]>t\[j\]) tmp=max(f\[j\],tmp);
}
}
printf("%d",ans);
return ; }
gugu Code
和LCIS完全一样的解法啊。
设f[i][j][0/1]表示第一个序列前i和第二个序列前j个位置，最后一个位置是上升还是下降，转移和之前一样，记录一个辅助数组即可。
注意这里是记方案数。
最基本的容斥模型：
给定一些条件, 问全部满足的对象的个数。
答案 = 所有对象 - 至少不满足其中一个的 + 至少不满足其中两个的 - 至少不满足其中三个的 +……
证明：考虑对于一个恰好不满足k个的的对象，被计算了几次。
显然只有当k=0时，这个对象才会被算进答案，所以我们就证明了上面这个容斥方法的正确性。
将上述式子*1^(k-i)，发现变成二项式定理！所以原式=（1-1）^k;
从n*m网格图的左下角走到右上角(n,m<=10^6),有t个坐标不能经过(t<=200),只能向上向右走,问有多少种不同的走法,对10^9+7取模。
那么这道题就可以用容斥来做。随意填-至少遇到一个障碍的方案数+至少遇到两个障碍的方案数-至少遇见三个障碍的方案数………………
给障碍点从左到右从下到上排个序,记f[i][j]表示走到了第i个障碍点且包括第i个点在内强制经过了j个障碍点的路径条数(除此之外也可能有经过的),枚举上一个经过的障碍点即可。
转移的时候乘上一个组合数表示从k到i的走法数目：
枚举倒数第二个走的障碍是哪个，然后用走到倒数第二个障碍的方案数f[k][j-1]*从倒数第二个障碍走到倒数第一个障碍的方案数；
最后统计答案：ans=f[n][0]-f[n][1]+f[n][2]……f[n][k];
另一种想法：
dp[i]表示第一个遇到的障碍物为i；
解释:第一部分，表示从起点走到障碍i的方案数。
第二部分，因为在障碍i左下角的障碍k，在计算第一部分时会被计算路径，这样就不满足我们的定义了，所以我们要减去从障碍k走到障碍i的路径数*从起点走到k的方案数；
所以最后答案是：
记忆化搜索：
在有一些dp问题中，状态之间的转移顺序不是那么确定，并不能像一些简单问题一样写几个for循环就解决了。
我们可以直接计算最终要求的状态，然后在求这个状态的过程中，要调用哪个子状态就直接调用即可，但是每一个状态调用一遍之后就存下来答案，下次计算的时候就直接取答案即可，就不需要从新再计算一遍。
虽然看上去每一次都计算不少，但是因为每一个状态都计算一次，所以均摊下来，复杂度还是状态数*状态转移。
给出一个n*m的网格，每次只能向右或者向下走，求从(1,1)走到(n,m)的方案数，其中有些位置是不能走的。
n,m<=1000
◦ 我们从另一个角度来思考这个问题。
◦我们用搜索算法来计算答案，先看看没有障碍的情况，有障碍只改一点。
然而搜索的时间复杂度是指数级的。
观察一下：这是有些重复计算的。
改成记忆化：
mp[x][y]==-1表示有障碍；
#include
using namespace std;
inline int read(){
int ans=;
char last=' ',ch=getchar();
while(ch>''||ch<'') last=ch,ch=getchar();
while(ch>=''&&ch<='') ans=(ans<<)+(ans<<)+ch-'',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
int n,m,t,p,x,y;
int mp[][];
int dp[][];
int dfs(int x,int y){
if(mp[x][y]==-) return ;
if(x==n&&y==m) return ;
if(dp\[x\]\[y\]!=-) return dp\[x\]\[y\];
int ans=;
if(x<n) ans+=dfs(x+,y);
if(y<m) ans+=dfs(x,y+);
dp\[x\]\[y\]=ans;
return ans; }
int main(){
n=read();m=read();
t=read();p=read();
memset(dp,-,sizeof(dp));
for(int i=;i<=t;i++){
x=read();y=read();
mp[x][y]=-;
}
cout<<dfs(,);
return ;
}
给定一个区域，由一个二维数组给出。数组的(i,j)代表点(i,j)的高度。我们要找一个最长的滑雪路径，注意滑雪只能从高往低处滑。
#include
using namespace std;
inline int read(){
int ans=;
char last=' ',ch=getchar();
while(ch>''||ch<'') last=ch,ch=getchar();
while(ch>=''&&ch<='') ans=(ans<<)+(ans<<)+ch-'',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
int r,c;
int mp[][],dp[][];
int dx[]={,,-,};
int dy[]={,,,-};
bool pan(int x,int y){
return x>&&y>&&x<=r&&y<=c;
}
int dfs(int x,int y){
if(x>r||y>c||x<||y<) return ;
if(dp[x][y]!=-) return dp[x][y];
int ans=;
for(int i=;i<;i++){
int xx=x+dx[i],yy=y+dy[i];
if(pan(xx,yy)&&mp[xx][yy]<mp[x][y]){
ans=max(ans,dfs(xx,yy)+);
}
}
dp[x][y]=ans;
return ans;
}
bool pand(int i,int j){
return mp[i][j]>=mp[i-][j]&&mp[i][j]>=mp[i][j-]&&mp[i][j]>=mp[i][j+]&&mp[i][j]>=mp[i+][j];
}
int main(){
int b,Ans=;
r=read();c=read();
for(int i=;i<=r;i++)
for(int j=;j<=c;j++)
mp[i][j]=read();
for(int i=;i<=r;i++)
for(int j=;j<=c;j++)
if(pand(i,j)) {
memset(dp,-,sizeof(dp));
b=dfs(i,j);
Ans=max(b,Ans);
}
cout<<Ans<<endl;
return ;
}
bzoj3810
n, m <= 300;k <= 10000
如果合法，一定有一条贯穿整个矩形的线；
dp[i][j][t]长度为i，宽度为j，面向大海的边的状态是t这样划分最小差异度是啥；、
然后因为一定要贯穿，可以一分为二：dp[i][j][t]=左边+右边；
其中t：
t==1 只有一面环海：
显然如果我们要将其分成两部分，只能：
for(int i=;i<n;i++) ans=min(ans,work(i,m,)+work(n-i,m,));
return f[n][m][t]=ans;
t==2 && t==4 有2面环海：
t==2：
如果要分成两部分的话，可以横着分，也可以竖着分：
for(int i=;i<n;i++) ans=min(ans,work(i,m,)+work(n-i,m,));//竖着分？
for(int i=;i<m;i++) ans=min(ans,work(n,i,)+work(m-i,n,));//横着分？t==4：
同样可以横着分和竖着分：
for(int i=;i<n;i++) ans=min(ans,work(i,m,)+work(n-i,m,));
for(int i=;i<m;i++) ans=min(ans,work(n,i,)+work(n,m-i,));
t==3:三面环海：
同样有两种划分方法：
for(int i=;i<n;i++) ans=min(ans,work(i,m,)+work(n-i,m,));
for(int i=;i<m;i++) ans=min(ans,work(n,i,)+work(n,m-i,));
主程序：
拓扑图的dp;
◦ 拓扑图dp通常是在拓扑图上求关于所有路径的某种信息之和。当然这里的“和”的运算法则可以是加法或是取max和min。或者其他定义的运算。
◦ 按拓扑序沿着有向边转移就可以了。
◦ 其实我们对于一般非有关期望和概率的dp，如果题目中每一个转移关系是双边的，那么如果我们把dp的每一个状态记为一个点， dp状态之间关系构成的图就是一个拓扑图。
◦ 拓扑图dp实际上就是已经给了我们这个拓扑关系了，也就不需要我们自己找了，其实是更简单。
BZOJ4562 食物链
◦ 给定n个点m条边的有向无环食物网，求其中有多少条极长食物链。
◦ n<=10^5，m<=2*10^5
dp[i]从入度为0的点，走到i的方案数：
dp[i]=Σdp[j],j->i可行；
设f[u]为以节点u为终点的食物链数量。
按照拓扑序的顺序转移即可。
#include
#include
#include
#include
#include
using namespace std;
inline int read(){
int ans=;
char last=' ',ch=getchar();
while(ch>''||ch<'') last=ch,ch=getchar();
while(ch>=''&&ch<='') ans=(ans<<)+(ans<<)+ch-'',ch=getchar();
if(last=='-') ans=-ans;
return ans;
}
int n,m;
int head[],in[],out[];
int ecnt;
struct node{
int to,nxt;
}e[];
void add(int from,int to){
++ecnt;
e[ecnt].to=to;
e[ecnt].nxt=head[from];
head[from]=ecnt;
in[to]++;
out[from]++;
}
int ans,f[];
void tp(){
queue
for(int i=;i<=n;i++)
if(!in[i]) {
if(out[i]){
q.push(i);
f[i]=;
}
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
f[v]+=f[u];in[v]--;
if(in[v]==) q.push(v);
}
}
for(int i=;i<=n;i++) if(!out[i]) ans+=f[i];
cout<<ans<<endl;
}
int main(){
n=read();m=read();
for(int i=,a,b;i<=m;i++){
a=read();b=read();
add(a,b);
}
tp();
}
经典题：
◦ 给一个n个点m条边的无向图，每一条边(u,v)有两个参数(len,cnt)表示边的长度以及边上不同的礼物数量，我们在每一个走过的边(u,v,len,cnt)只能选1个礼物，选择的方案数是cnt。
◦ 我们现在想从S走到T，我们想要求出在只走最短路径的情况下有多少种选择的礼物的方案数。
◦ 一条路径选择礼物的方案数就是每条边的cnt的乘积。答案对一个大质数取模。
◦ n<=100000,m<=300000
◦ u,v,len,cnt)其实就是(u,v)点对有cnt条长度len为边，求S到T的最短路径方案数。
◦ 求以最短路径为前提的一些问题，果断先建最短路图。
◦ 毕竟，最短路图建出来是一个DAG，而DAG就比随意的图具有更好的性质，不求白不求。
◦ 然后就是求DAG上从S到T，路径的方案数。
◦ 设f[u]为从u到T路径的方案数，
◦ 答案就是f[S]。
手机扫一扫
移动阅读更方便
你可能感兴趣的文章