CFR 545 C. Woodcutters ( DP )

Problem - 545C - Codeforces
題意：
在一維空間中給一堆樹，用位置和高度描述。現在要砍樹，砍完可以選擇向其左方或右方倒，倒完後高度就會往那方向躺平佔據區間。求可以砍多少樹，使得任意點不被兩棵樹同時佔據。
解法：
dp[ i ][ j ] : 考慮前 i 棵樹，最後一棵樹沒砍 / 往左倒 / 往右倒，這樣狀態時最多可以砍多少樹。
狀態轉移很容易考慮，詳見代碼。

int N;
vi X, H;

void init(){
	cin >> N;
	X = H = vi( N );
	for( int i = 0; i < N; ++i )
		cin >> X[ i ] >> H[ i ];
}

void preprocess(){

}

void solve(){
	vvi dp( N + 1, vi( 3 ) );
	dp[ 1 ][ 1 ] = 1; // turn to left
	for( int i = 1; i < N; ++i ){
		upmax( dp[ i + 1 ][ 0 ], max( dp[ i ][ 0 ], max( dp[ i ][ 1 ], dp[ i ][ 2 ] ) ) );
		if( X[ i - 1 ] < X[ i ] - H[ i ] )
			upmax( dp[ i + 1 ][ 1 ], dp[ i ][ 0 ] + 1 ),
			upmax( dp[ i + 1 ][ 1 ], dp[ i ][ 1 ] + 1 );
		if( X[ i - 1 ] + H[ i - 1 ] < X[ i ] - H[ i ] )
			upmax( dp[ i + 1 ][ 1 ], dp[ i ][ 2 ] + 1 );
		if( i + 1 == N or X[ i ] + H[ i ] < X[ i + 1 ] )
			upmax( dp[ i + 1 ][ 2 ], dp[ i + 1 ][ 0 ] + 1 );
	}
	cout << max( dp[ N ][ 0 ], max( dp[ N ][ 1 ], dp[ N ][ 2 ] ) ) << endl;
}