http://codeforces.com/contest/545/problem/C
题目大意：
给n棵树的在一维数轴上的坐标，以及它们的高度。现在要你砍倒这些树，树可以向左倒也可以向右倒，砍倒的树不能重合、当然也不能覆盖其他的树原来的位置，现在求最大可以砍倒的树的数目
思路:从左往右dp，f[i][0]代表i不砍，f[i][1]代表砍了往左倒，f[i][2]代表砍了向右倒。
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 #include<cstring> 5 #include<iostream> 6 #define ll long long 7 ll a[200005],h[200005]; 8 int f[200005][3],n; 9 int read(){ 10 int t=0,f=1;char ch=getchar(); 11 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} 12 while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} 13 return t*f; 14 } 15 int main(){ 16 n=read(); 17 for (int i=1;i<=n;i++) a[i]=read(),h[i]=read(); 18 a[0]=-99999999999LL; 19 for (int i=1;i<=n;i++){ 20 f[i][0]=std::max(f[i-1][0],f[i-1][1]); 21 if (a[i-1]+h[i-1]<a[i]) f[i][0]=std::max(f[i][0],f[i-1][2]); 22 23 if (a[i]-h[i]>a[i-1]) 24 f[i][1]=std::max(f[i-1][0],f[i-1][1])+1; 25 if (a[i]-h[i]>a[i-1]+h[i-1]) 26 f[i][1]=std::max(f[i][1],f[i-1][2]+1); 27 28 f[i][2]=std::max(f[i-1][0],f[i-1][1])+1; 29 if (a[i-1]+h[i-1]<a[i]) 30 f[i][2]=std::max(f[i][2],f[i-1][2]+1); 31 } 32 int ans=std::max(f[n][0],std::max(f[n][1],f[n][2])); 33 printf("%d ",ans); 34 return 0; 35 }