#include #include #include #include #include #include #include #include #include #include #define INF 100000000 using namespace std; struct node{ int x,y; }; node a[1005]; int n; int ma[1005][1005]; int dp[1005]; void print(int max,int q){ if(max == 1){ printf("%d\n",q+1); return ; } printf("%d\n",q+1); for(int i = 0;i < n;i++){ if(ma[q][i] && dp[i] == max-1){ print(max-1,i); break; } } } int fun(node &x,node &y){ if(x.x < y.x && x.y > y.y) return 1; return 0; } int dfs(int cur){ int& ret = dp[cur]; if(ret > 0) return ret; ret = 1; for(int i = 0;i < n;i++){ if(ma[cur][i]){ ret = max(dfs(i)+1,ret); } } return ret; } int main(){ while(scanf("%d%d",&a[n].x,&a[n].y)!=EOF) n++; memset(ma,0,sizeof(ma)); for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ if(fun(a[i],a[j]) > 0){ ma[i][j] = 1; } } } for(int i = 0;i < n;i++){ dfs(i); } int maxn; int max = -1; for(int i = 0;i < n;i++){ if(dp[i] > max){ maxn = i; max = dp[i]; } } cout << max << endl; print(max,maxn); return 0; }
POJ 3321 Apple Tree (樹狀數組) &
函數模板在實際程序中應用比較廣泛，這是由於它本身的特性
指針與數組 指針與其它數據結構呢？比如說鏈表？ 存儲空間
HDU 4923 Room and Moor 貪心+棧
MFC 直線 虛線 折線 圓 橢圓 矩形 弧形 ****
好久沒有做算法題了，重溫幾個簡單的算法題。 第一題：求
