线性动态规划入门题

很容易发现第 i 课树很难对第 i+2 课树造成相应的影响，因此我们的状态可以直接压缩成前后关联的形式

考虑 f[i][0/1] 表示决策第 i 棵树后，其选择向左倒或站立/向右倒后的最优答案，递推公式是显然的

代码

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define foR(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=1e5+5;
int x[N],h[N];
int f[N][2];
int n;
signed main() {
	cin>>n;
	For(i,1,n) scanf("%lld%lld",&x[i],&h[i]);
	x[n+1]=inf;
	f[1][0]=1;	
	For(i,2,n) {
		int x0=0,x1=0;
		//k=0
		//上一个位置如果不砍倒 
		if(x[i-1]+h[i-1]<x[i]-h[i]) x1=1;
		if(x[i-1]<x[i]-h[i]) x0=1;
		f[i][0]=max(f[i][0],f[i-1][0]+x0);
		f[i][0]=max(f[i][0],f[i-1][1]+x1);
		
		//k=1
		if(x[i]+h[i]<x[i+1]) {
			f[i][1]=max(f[i][1],f[i-1][0]+1);
			f[i][1]=max(f[i][1],f[i-1][1]+1);
		}
		else f[i][1]=-inf;
	}
	cout<<max(f[n][0],f[n][1]); 
	return 0;
}