贪心算法： 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 ;
}