HDU 1087 1160

HDU 1087 Super Jumping!

（和最大）递增子序列

题目链接

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    while(~scanf("%d", &n) && n)
    {
        int a[1005];
        for(int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        long long dp[1005];
        memset(dp, 0, sizeof(dp));
        long long ans = 0;

        for(int i = 0; i < n; ++i)
        {
            dp[i] = a[i];
            for(int j = 0; j < i; ++j)
                if(a[j] < a[i])
                    dp[i] = max(dp[i], dp[j] + a[i]);
            ans = max(dp[i], ans);
        }

        cout << ans << '\n';
    }
    return 0;
}

HDU 1160 FatMouse’s Speed

w（重量）递增前提下 s（速度）递减的mouse最多有多少只，分别是哪几只

先按前提条件排序，再dp并记录路径

题目链接

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

struct node
{
    int w, s, num;
} a[1005];

int dp[1005];
int pre[1005];
bool cmp(node a, node b)
{
    if(a.w != b.w)
        return a.w < b.w;
    else
        return a.s > b.s;
}

int main()
{
    memset(pre, -1, sizeof(pre));
    int cnt = 1;
    while(~scanf("%d%d", &a[cnt].w, &a[cnt].s))
        {
            a[cnt].num = cnt;
            cnt++;
///不要跟上面写在一起（程序由右向左执行,[]里的cnt也变了）
        }
    sort(a + 1, a + cnt, cmp);
    int ans = 0;
    int pos;
    for(int i = 0; i < cnt; ++i)
    {
        dp[i] = 1;
        for(int j = 0; j < i; ++j)
            if(a[j].w < a[i].w && a[j].s > a[i].s)
                if(dp[i] < dp[j] + 1)
                {
                    dp[i] = dp[j] + 1;
                    pre[ a[i].num ] = a[j].num;
                }
        if(dp[i] > ans)
        {
            ans = dp[i];
            pos = a[i].num;
        }
    }
    vector<int> vec;
    while(pos != -1)
    {
        vec.push_back(pos);
        pos = pre[pos];
    }
    cout << ans << '\n';
    for(int i = vec.size() - 1; i >= 0; --i)
        cout << vec[i] << '\n';
    return 0;
}