期末集训总结

这个学期我们主要学了四个内容：序列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;
}