当前位置：首页 > news >正文

OI学习笔记（二）

news 2026/4/25 22:09:49

前言

本文为一名Oier的真实学习笔记，如果对文中有问题或有意见，欢迎联系我
本篇专门介绍 dp。

序列 dp

概念之类的就不说了。
例题：P1002 [NOIP 2002 普及组] 过河卒

思路先弱化问题，先不考虑马的存在。
由于每一次卒只能向下或者向右。
记从 (i,j) 出发，到达终点的路径条数为 \(f_{i,j}\)。
根据分类计数原理：
1. 往右走，可以到达 (\(i,j+1\))。
2. 往下走，可以到达 (\(i+1,j\))。
则得到递推关系式：\(f_{i,j}=f_{i,j+1}+f_{i+1,j}\)。
递推初值：\(f{n,m}=1\)。
由于需要根据较大行、较大列的 f 值推出较小行、较小列的 f 值，因此行和列需要逆序枚举。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 110
#define ll long long
int dx[8]={2,1,-1,-2,-2,-1,1,2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};
bool vis[MAXN][MAXN];
ll f[MAXN][MAXN];
int n,m,x,y;
int main(){scanf("%d%d%d%d",&n,&m,&x,&y);vis[x][y]=true;for(int i=0;i<8;++i){if(x+dx[i]>=0&&x+dx[i]<=n&&y+dy[i]>=0&&y+dy[i]<=m)vis[x+dx[i]][y+dy[i]]=true;}f[n][m]=1;for(int i=n;i>=0;i--)for(int j=m;j>=0;j--){if(i==n && j==m) continue;if(vis[i][j])f[i][j]=0;else f[i][j]=f[i+1][j]+f[i][j+1];  	}printf("%lld\n",f[0][0]);return 0;
}

P1216 [IOI 1994 / USACO1.5] 数字三角形 Number Triangles

思路递推实现（动态规划）

int i,j;
for(j=1;j<=n;j++) d[n][j]=a[n][j];
for(i=n-1;i>=1;i--)for(j=1;j<=i;j++)d[i][j]=a[i][j]+max(d[i+1][j],d[i+1][j+1]);

时间复杂度：\(O(n^2)\)
使用动态规划（递推）的写法要保证 \(d_{i,j}\) 之前，已经计算出 \(d_{i+1,j}\) 和 \(d_{i+1,j+1}\)。

#include<bits/stdc++.h>
#define maxn 510
using namespace std;
int d[maxn][maxn],a[maxn][maxn];
int n;
int max(int a,int b){return a>b?a:b;
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)scanf("%d",&a[i][j]);d[1][1]=a[1][1];for(int i=2;i<=n;i++)for(int j=1;j<=i;j++)d[i][j]=max(d[i-1][j],d[i-1][j-1])+a[i][j];int ans=0;for(int i=1;i<=n;i++) ans=max(ans,d[n][i]);printf("%d",ans);return 0;

LIS(最长上升子序列)问题
B3637 最长上升子序列
思路
建立一个数组 \(s_k\) 来储存所有长度为 \(k\) 的最长上升子序列的最后一个数字的最小值。即
用数学表达式写即为：\(s_k=min(b_j( F_j=k,1 \le j \le i))\)。
\(s_k\) 能发现什么性质？
\(s_k\) 是单调递增的！
定义 \(s[k]\) 表示 lis 长度为 \(k\) 的序列中，序列最后一个数字的最小值为 \(s[k]\)。
考虑使用反证法：如果 \(i<j\)，而 \(s_i>s_j\)：
由于长度为 j 的 lis 一定包含长度为 i 的情况，所以一定可以找到一个 \(m\)，使得 \(m<s[j]\) ,且以 \(m\) 结尾的序列 lis 值为 \(i\)。
这与 lis 为 \(i\) 的序列中最后一个数字最小为 \(s_i\) 矛盾(因为 \(m\) 比 \(s_i\) 更小)。
单调性得证！
所以在求 \(f_i\) 值时，只需二分查找一个最大的 \(j\)，使得 \(s_j<b_i\)，则表示 \(b_i\) 可以跟在 \(s_j\) 后面，形成一个上升子序列，所以 \(f_i=j+1\)。
演示一下：

i	1	2	3	4	5	6
\(b_i\)	3	7	2	4	6	8
\(F_i\)	1

k	1
\(s_k\)	1

i	1	2	3	4	5	6
\(b_i\)	3	7	2	4	6	8
\(F_i\)	1	2

k	1	2
\(s_k\)	1	7

i	1	2	3	4	5	6
\(b_i\)	3	7	2	4	6	8
\(F_i\)	1	2	1

k	1	2
\(s_k\)	1	7

i	1	2	3	4	5	6
\(b_i\)	3	7	2	4	6	8
\(F_i\)	1	2	1	2

k	1	2
\(s_k\)	1	7

i	1	2	3	4	5	6
\(b_i\)	3	7	2	4	6	8
\(F_i\)	1	2	1	2	3

k	1	2	3
\(s_k\)	1	7	6

i	1	2	3	4	5	6
\(b_i\)	3	7	2	4	6	8
\(F_i\)	1	2	1	2	3	4

k	1	2	3	4
\(s_k\)	1	7	6	8

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 1000005;
int n,a[MAXN],dp[MAXN],R,l,r,ans;int main(){cin >> n;for(int i = 1;i <= n;++i){cin >> a[i];}dp[0]=0;R=0;for(int i=1;i<=n;++i){if(a[i]>dp[R]){dp[R+1]=a[i];R++;}else{l=0;r=R;while (l<=r){int mid = l + r>>1;if (dp[mid] < a[i])l = mid+1;else {ans=mid;r = mid-1; }}//循环结束后，r=l+1,l指向最右边一个小等于x的数，r指向最左边一个大于x的数。dp[ans]=a[i];}}int t = 0;for(int i = 1;i <= n;++i){if(dp[i]!=0)t++;}cout << t << endl;return 0;
}

最优子结构
原问题最优，当且仅当子问题最优。
大问题的最优解可以由小问题的最优解推出，这个性质叫做最优子结构性质。
DP 三连
设计 DP 算法，往往可以遵循 DP 三连：
我是谁？ —— 设计状态，表示局面
我从哪里来？
我要到哪里去？ —— 设计转移
如何学好 DP
未来将讲到 DP 的各种优化。
e.g. 数据结构优化、斜率优化。
一般而言，DP 的难点，在初学时是如何设计状态；在学习深入一些之后，变成了如何设计转移；在省选 / NOI 级别，又变成了如何设计状态。
学习 DP 主要靠做题练习。有一些设计状态的思想，需要在具体题目中总结。
线性（序列）模型
线性模型的是动态规划中最常用的模型，上例讲到的最长单调子序列就是经典的线性模型，这里的线性指的是状态的排布是呈线性的。
本类的状态是基础中的基础，大部分动态规划都要用到它，成为一个维。
常见的状态设计：