贪心算法： Codevs 1052 地鼠游戏

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <vector>

using namespace std;

const int maxn =  + ;

struct Mice {

    int value;

    int time;

    Mice(int v = , int t = ) : value(v), time(t) {}

    //需要对时间进行排序 -- 升序

    friend operator < (const Mice& a, const Mice& b) {

        return a.time < b.time;

    }

} game[maxn];

int dp[maxn], time, ans;

void solve();

void solve()

{

    int n;

    memset(dp, , sizeof(dp));

    scanf("%d", &n);

    for (int i = ; i < n; i++) {

        scanf("%d", &game[i].time);

    }

    for (int i = ; i < n; i++) {

        scanf("%d", &game[i].value);

    }

    //按时间升序 排序

    sort(game, game + n);

    for (int i = ; i < n; i++)

    {

        //时间小的开始打

        for (int j = game[i].time; j >= ; j--) {

            // i当前最小时间, j为动态的时间,比较每秒

            //和 下一秒and当前最小的 价值

            //因为时间在减少 ∴应该是 j-1 + 当前时间的价值

            //向前走

            dp[j] = max(dp[j], dp[j - ] + game[i].value);

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

        }

    }

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

}

int main()

{

    solve();

    return ;

}