首页 > 代码库 > 4D-最长上升子序列

4D-最长上升子序列

给你N信封和1张卡片,让你从左到右选择信封(要求是右信封比左信封大)且最左边的信封要能装进卡片

#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;struct Node{    int si, sj;    unsigned short n;};Node Susake[5002];int short dp[5002][5002], b[5002], xx[5002];//pathint comp(Node a, Node b){    return a.sj > b.sj ? 0 : 1;}int main(int argc, char *argv[]){    int n, si, sj, Max, fi, fj, ei, ej, k;    while(scanf("%d%d%d", &n, &si, &sj) != EOF)    {        memset(Susake, 0, sizeof(Susake));        memset(dp, 0, sizeof(dp));        memset(b, 0, sizeof(b));        memset(xx, 0, sizeof(xx));        for(int i = 1; i <= n; i++)        {            scanf("%d%d", &Susake[i].si, &Susake[i].sj);            Susake[i].n = i;        }        sort(Susake + 1, Susake + n + 1, comp);        Max = 0;        for(int i = 1; i <= n; i++)        {            for(int j = 1; j <= i; j++)            {                if(Susake[i].si > Susake[j].si && Susake[i].sj > Susake[j].sj &&                   Susake[i].si > si && Susake[j].si > si &&                   Susake[i].sj > sj && Susake[j].sj > sj)                    dp[i][j] = b[j] + 1;                else if(Susake[i].si <= si || Susake[i].sj <= sj)                    dp[i][j] = 0;                else                    dp[i][j] = 1;                if(b[i] < dp[i][j])                {                    b[i] = dp[i][j];                    xx[i] = j;                }                if(Max < dp[i][j])                {                    ei = i; ej = j;//ei                    Max = dp[i][j];                }            }        }        xx[1] = 1;        if(Max)        {            printf("%d\n", Max);            k = 1;            b[k] = Susake[ei].n;            if(Max == 1)                printf("%d\n", b[1]);            else            {                while(1)                {                    if(dp[ei][ej] == 1) break;                    ei = ej;                    ej = xx[ej];                    k++;                    b[k] = Susake[ei].n;                }                for(int i = k; i >= 2; i--)                    printf("%d ", b[i]);                printf("%d\n", b[1]);            }        }        else printf("0\n");    }    return 0;}

 

4D-最长上升子序列