基于贪心的DP

概念：贪心和DP的关系

贪心和DP严格来讲都不是算法，而是一种解决问题的思路。

不一样的是，贪心每次选择的都是局部最优解，而DP则是考虑所有需要考虑的状态后得到全局最优解。

贪心的缺点：有时候无法取得最优解。

DP的缺点：有时候时空效率过低。

因此可以在DP的过程中，应用贪心策略进行优化。

例题

1. P4823 [TJOI2013] 拯救小矮人

先按 $A_i+B_i$ 排序，小的先出去，然后进行DP（背包）。

状态：f[i][j]表示排序后的前 $i$ 个人走掉 $j$ 个时，人梯剩余的最大高度，其中第一维可以压缩掉。

边界：$f[0]=\sum A_i$。

目标：当 $f[i] \ge 0$ 时，$i$ 的最大值

转移方程：$f[j]=\max(f[j],f[j-1]-A_i)$

时间复杂度 $O(n^2)$。

本题还有 $O(n\log n)$ 的贪心+优先队列做法。

2. P2370 yyy2015c01的U盘

3. P2577 [ZJOI2004] 午餐

# include<iostream>
# include<algorithm>
# include<cstring>
using namespace std;

const int N=203;

struct stu{
	int a,b;
	void in(){
		cin>>a>>b;
	}
}p[N];

int n,ans=1e9,sum[N]; //前i人打饭时间总和 
int f[N][N*N]; //前i人打饭，在1号窗口打饭时间j，这i人吃饭时间min

bool cmp(stu x,stu y){
	return x.b>y.b;
}

int main(){
	cin>>n;
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<=n;++i)
		p[i].in();
	sort(p+1,p+1+n,cmp);
	for(int i=1;i<=n;++i)
		sum[i]=sum[i-1]+p[i].a;
	for(int i=1;i<=n;++i)
		for(int j=0;j<=sum[i];++j){
			if(j>=p[i].a)
				f[i][j]=min(f[i][j],max(f[i-1][j-p[i].a],j+p[i].b));
			f[i][j]=min(f[i][j],max(f[i-1][j],sum[i]-j+p[i].b));
		}
	for(int i=0;i<=sum[n];++i)
		ans=min(ans,f[n][i]);
	cout<<ans;
	return 0;
}

4. P5020 货币系统

实际上我们就是要从数组 $a$ 中去掉能用其他元素组合而表示出来的元素，剩下的数组成数组 $b$。

那么可以先从小到大排序，然后利用完全背包检验。

5. CF1332D Walk on Matrix

6. [SCOI2008] 配对

小结

基本方法：

1. 对物品先排序再进行DP。
2. 在最优解一定具有某种结构时，可以利用这个结构来优化DP。（先想性质再DP）

作业