読者です 読者をやめる 読者になる 読者になる

JOI 2010 春合宿 day4-3 「lake」

JOI

円を切って伸ばして直線にする発想はすぐ思いついたけど、そこからなんか詰まった。
が、なんのこっちゃない単なるDPだったorz

#include<cstdio>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i < n; i++)
#define pb push_back
using namespace std;

int tra[500000], s[2000], t[2000], w[4000], dp[4000][4000];

int main(){
	int n, n2;
	vector<int> d;
	
	scanf("%d",&n);
	n2 = 2*n;
	
	rep(i,n){
		scanf("%d%d", &s[i], &t[i]);
		d.pb(s[i]); d.pb(t[i]);
	}
	
	sort(d.begin(), d.end());
	
	rep(i,d.size()) tra[d[i]] = i;
	
	rep(i,n){
		w[tra[s[i]]] = tra[t[i]] - tra[s[i]];
		w[tra[t[i]]] = tra[s[i]] - tra[t[i]];
	}
	
	
	rrep(i,n2){
		rep(j,n2-i){
			dp[i][j] = max(dp[i-1][j], dp[i-1][j+1]);
			
			if(w[j] == i) dp[i][j]++; else {
				
				if(w[j] > 0 && w[j] < i) dp[i][j] = max(dp[i][j], dp[w[j]][j] + dp[i-w[j]][j+w[j]]);
				if(w[j+i] < 0 && w[j+i] > -i) dp[i][j] = max(dp[i][j], dp[-w[j+i]][j+i+w[j+i]] + dp[i+w[j+i]][j]);
			}
		}
	}
	
	printf("%d\n", dp[n2-1][0]);
	
	return 0;
}