円を切って伸ばして直線にする発想はすぐ思いついたけど、そこからなんか詰まった。
が、なんのこっちゃない単なる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; }