HDU - 1160 FatMouse's Speed 【DP】

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1160

题意

给出一系列的 wi si

要找出一个最长的子序列满足

wi 是按照升序排列的

si 是按照降序排列的

思路

因为有双关键词

我们可以先将一关键词比如 W 按照升序排序

再根据 S 关键词来找最长下降子序列就可以了

要输出其中的一个子序列我们只要记录其父节点就可以

再循环网上找

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <list>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a, b) memset(a, (b), sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = acos(-1.0);

const double E = exp(1.0);

const double eps = 1e-8;

const int INF = 0x3f3f3f3f;

const int maxn = 1e3 + 5;

const int MOD = 1e9 + 7;

struct node

{

    int w, s;

    int id;

}q[maxn];

bool comp(node x, node y)

{

    if(x.w == y.w)

        return x.s > y.s;

    return x.w < y.w;

}

int dp[maxn];

int pre[maxn];

int main()

{

    int pos = 1;

    while (~scanf("%d%d", &q[pos].w, &q[pos].s))

        q[pos].id = pos++;

    sort(q, q + pos, comp);

    int ans = 1;

    CLR(dp, 0);

    CLR(pre, 0);

    for (int i = 1; i <= pos; i++)

    {

        dp[i] = 1;

        for (int j = 1; j < i; j++)

        {

            if (q[i].s < q[j].s && q[i].w > q[j].w)

            {

                if (dp[j] + 1 > dp[i])

                {

                    dp[i] = dp[j] + 1;

                    pre[i] = j;

                }

            }

        }

        ans = max(ans, dp[i]);

    }

    printf("%d\n", ans);

    vector <int> v;

    for (int i = 1; i <= pos; i++)

    {

        if (dp[i] == ans)

        {

            int vis = i;

            v.pb(q[vis].id);

            while (pre[vis])

            {

                v.pb(q[pre[vis]].id);

                vis = pre[vis];

            }

            break;

        }

    }

    vector <int>::iterator it;

    for (it = v.end(), it--; ; it--)

    {

        printf("%d\n", *it);

        if (it == v.begin())

            break;

    }

}

巴特西

HDU - 1160 FatMouse's Speed 【DP】

最新文章

热门文章