dp学习笔记

endswitch / 2023-08-23 / 原文

前言：因为本人 \(dp\) 实在太差了，故此挖个新坑。

\(dp\) 的基本技巧：

设计状态，要注意一定要不重不漏，所有能影响到答案的数据都要包含到状态里面。
初始化，基本上是第一项
转移，要注意无后效性，面面俱到。
可以关注数据范围，有时候范围会给我们以提醒。
状态设计：一个条件，一个维度
增加条件，增加维度，改变状态（无后效性）。
求方案数的一般思路是在开一个与之对应的数组。
改变顺序，
消除冗余状态，简化空间（乌龟棋）
循环顺序的界定由转移的顺序决定。
把转移方程写下来之后再去写代码。
用所学过数学模型进行分析

多说无益，真正的还是需要通过做题总结。所以以下就用来写做题总结。

P1233 木棍加工

其实第一眼想到的是一直去跑最长上升子序列直到序列中没有上升子序列，但是这样及其复杂而且难实现。观察题目，发现题目是一个最优性问题，因此我们不难想到排序。以 \(l\) 为第一关键字，\(r\) 为第二关键字从大到小排序然后再跑一遍最长上升子序列即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=50005;
struct Node {int l,w;} a[N];
int n,cnt,ans,dp[N];
inline bool cmp(Node a,Node b) {
	if(a.l==b.l) return a.w<b.w;
	else return a.l<b.l;
}
signed main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n,cnt=n;
	for(int i=1;i<=n;i++)
		cin>>a[i].l>>a[i].w,dp[i]=1;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=i-1;j++)
			if(a[j].w>a[i].w) dp[i]=max(dp[i],dp[j]+1);
		ans=max(ans,dp[i]);
	}
	cout<<ans;
	return 0;
}