首页 > 代码库 > codeforces4D - Mysterious Present DP

codeforces4D - Mysterious Present DP

2024-07-15 19:04:27   213人阅读

题意：求限定起始位置的二维最长递增子序列.

解题思路：直接DP

解题代码：

  1 // File Name: 4d.cpp  2 // Author: darkdream  3 // Created Time: 2014年08月04日 星期一 19时24分49秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25  26 using namespace std; 27  28 struct node{ 29   int from; 30   int len; 31 }dp[5000]; 32 struct node1{ 33   int w, h,s;  34 }a[5005]; 35 int ok[10000]; 36 int cmp(node1 a,node1 b) 37 { 38    if(a.w == b.w)  39        return a.h < b.h; 40    return a.w < b.w; 41 } 42 void dfs(int k) 43 { 44   if(k == -1) 45       return;  46    dfs(dp[k].from); 47    if(a[k].s) 48    printf("%d ",a[k].s); 49  50 } 51 int main(){ 52    int n ; 53    scanf("%d %d %d",&n,&a[0].w,&a[0].h); 54    memset(ok,0,sizeof(ok)); 55    for(int i =1 ;i <= n;i ++) 56    { 57        scanf("%d %d",&a[i].w,&a[i].h); 58        a[i].s = i;  59    } 60    sort(a+1,a+1+n,cmp); 61  /*  for(int i = 1;i <= n;i ++) 62    { 63        printf("%d %d\n",a[i].w,a[i].h); 64    }*/ 65    for(int i = 0 ;i <= n;i ++) 66    { 67       dp[i].from = i ;  68       dp[i].len = 1;  69    } 70    dp[0].from = -1; 71    ok[0] = 1;  72    int asite = 0; 73    int amx = 1;  74    for(int i = 1;i <= n;i ++) 75    { 76       int mx = 0; 77       int site = -1 ;  78       for(int j = 0;j < i;j ++) 79       { 80         if(a[i].w > a[j].w && a[i].h > a[j].h && ok[j]) 81         { 82             ok[i] = 1;  83             if(dp[j].len > mx) 84             { 85                mx = dp[j].len; 86                site = j; 87             } 88         } 89       } 90       dp[i].len = mx +1;  91       dp[i].from = site;     92       if(dp[i].len > amx) 93       { 94         amx = dp[i].len ;  95         asite = i;  96       } 97       //printf("%d\n",dp[i].len); 98    } 99    printf("%d\n",amx-1);100    dfs(asite);101 return 0;102 }
View Code

 


联系
我们