这个学期我们主要学了四个内容：序列DP，背包DP，区间DP，最短路。
序列DP
最长公共子序列
朴素模版
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if (a[i]==b[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]);
}
}
最长上升/下降子序列
朴素模版
for (int i=1;i<=n;i++){
for (int j=1;j<i;j++){
if (a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);
}
}
二分优化
for (int i=1;i<=n;i++){
if (a[i]>dp[cnt]) dp[++cnt]=a[i];
else{
int l=1,r=cnt,pos=0;
while (l<=r){
int mid=(l+r)>>1;
if (a[i]<=dp[mid]){
r=mid-1;ans=mid;
}else l=mid+1;
}
dp[pos]=a[i];
}
}
背包DP
背包DP一般有两种属性，体积 \(v\) 和价值 \(w\)，通常用DP或搜索求解。
01背包
顾名思义，每个物品只有选和不选两种状态，转移方程很好得：
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v]+w)
可以滚动掉第一维：
dp[i]=max(dp[i],dp[j-v]+w)
滚动后要倒着枚举，否则会影响答案。
完全背包
可以选无数次物品。
dp[i][j]=max(dp[i-1][j],dp[i][j-v]+w)
多重背包
多了一个属性：数量 \(s\)
朴素做法
直接挨个枚举，时间复杂度为 \(O(W\sum_{i=1}^{n}s_i )\)，无法接受。
有二进制分组优化、单调队列优化等优化方法。
区间DP
区间DP是一类以区间作为状态进行转移的动态规划，由于要对区间进行DP，所以时间复杂度通常为 \(O(n^2)\) ~ \(O(n^3)\) 左右。
在求解时，通常在区间内枚举断点，再合并断点两边的区间以获得最优解。
for (int len=2;len<=n;len++){
for (int i=1;i<=n-len+1;i++){
int j=i+len-1;
for (int k=i;k<j;k++){
dp[i][j]=min(dp[i][k]+dp[k+1][j]+cost(i,j));
}
}
}
最短路
图论可比DP好玩多了
存图
一般是邻接矩阵、邻接表、链式前向星三种，因为cache的机制，vector有时候会比链式前向星快
求最短路
Dijkstra
图中不能有负权边
void dijsktra(int st){
priority_queue<PII,vector<PII>,greater<PII>> q;
q.push({0,st});
dis[st]=0;
while (!heap.empty()){
PII t=q.top();q.pop();
int u=t.second;
if (vis[u]) continue;
vis[u]=true;
for (auto p:g[u]){
int v=p.second,w=p.first;
if (dis[u]+w<dis[v]){
dis[v]=dis[u]+w;
q.push({dis[v],v});
}
}
}
}
Bellman-Ford
可以用来判负环
bool bellmanford(int n,int s){
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
bool flag;
for (int i=1;i<=n;i++){
flag=0;
for (int u=1;u<=n;u++){
if (dis[u]==0x3f3f3f3f) continue;
for (auto p:g[u]){
int v=p.first, w=p.second;
if (dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
flag=1;
}
}
}
if (!flag) break;
}
return flag;
}