dp做题笔记

1. P4310
   很自然想到可以类比求最长不上升子序列来进行dp。然而 $O(n^2)$ 的复杂度不能通过。看了题解之后才发现，可以考虑什么样的数可以转移到当前枚举到的数。将当前枚举到的数化为二进制，如果这一位上是1，那么之前所有二进制这一位是1的数都可以转移到当前枚举到的数。所以可以设置 $dp[i]$ 表示第i位上是1的数结尾的最长子序列长度。时间复杂度 $O(31n)$
2. P1772
   因为提前知道是dp题，所以开始思考转移方程怎么写。但感觉改变路线会增加花费这一点是有后效性的。最终还是看了题解。状态转移方程：$dp[i]=min(dp[i],dp[j]+k+co[j+1,i]*(i-j))$，$dp[i]$ 表示到第i天最小花费。我们可以枚举哪一天改变了路线。$j$天之前怎么走的路线不管，然后 $j+1$ 天改变路线，从 $j+1$ 天到 $i$ 天都走一条路线。这样搭配最短路即可
3. P1941
   看到题很容易想到了dp怎么写。但是这题的细节问题较多，花了很多时间去调试和思考。然而最后只得了65分，有tle也有wa。
   最终还是看了题解，这道题有点背包dp的感觉。感觉状态转移很巧妙，特地记下来

cpp
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
	memset(dp,0x3f,sizeof(dp));
	for(int s=1;s<=m;s++) dp[0][s]=0;
	for(int i=1;i<=n;i++){
		//技巧:对于超过m的都算作m，我们可以在m的上方保留一些范围 
		for(int j=up[i-1]+1;j<=m+up[i-1];j++){
			//技巧:对于可以进行多次的操作，不要去枚举进行了多少次，而是向下面，类似于完全背包这样 
			dp[i][j]=min(dp[i-1][j-up[i-1]]+1,dp[i][j-up[i-1]]+1);
		}
		//对应上面的，把m上方的保留区间都归到m上 
		for(int j=m+1;j<=m+up[i-1];j++){
			dp[i][m]=min(dp[i][m],dp[i][j]);
		}
		//很一般的转移 
		for(int j=1;j<=m-down[i-1];j++){
			dp[i][j]=min(dp[i][j],dp[i-1][j+down[i-1]]);
		}
		//技巧:我们可以把没有任何限制的情况下的dp表推出来
		//     然后再处理不能被转移到的地方 
		//     而不是直接就考虑那个地方不能被转移 
		for(int j=1;j<=lima[i];j++){
			dp[i][j]=inf;
		}
		if(limb[i]){
			for(int j=limb[i];j<=m;j++){
				dp[i][j]=inf;
			}
		}
	}