题目描述：
一支球队，长度为 $ n $ ，每个球员有 $ score[i],age[i] $ 。如果年龄较小的球员的分数严格大于一名年龄较大的球员，则存在矛盾。同龄没有矛盾。返回可能的无矛盾球队中得分最高的分数。
数据范围：
$ 1\le n \le 1000,1\le scores[i] \le 10^6,1\le ages[i] \le 1000 $
题解：
很容易想到使用动态规划解决，设计状态 $ dp[i] $ 表示选择 $ i $ 号球员时能得到的最大分数。首先排序，按照年龄或者按照分数（这里先按照年龄排序）。这样的话可以得到递推方程
可以发现 $ dp[i] $ 的值只与当前值和 $ [0, scores[i]] $ 区间中分数的最大值有关。所以可以使用序列数据结构维护该区间最值（使用线段树或者树状数组）。由于 $ scores $ 的数据范围大一些，所以可以考虑维护 $ age $ 。也可以考虑离散化 $ scores $ 。
按照分数排序，得到新的对偶的方程
这样的话只需要维护 $ age $ 就行了。试试树状数组，线段树写的太多了。
类似线段树优化dp的题目：
Problem - 4521 (hdu.edu.cn)
B-卡牌对战游戏_华为杯中国地质大学(武汉)第十七届ICPC程序设计大赛暨 华中地区部分高校第十五届ICPC邀请赛竞赛 (nowcoder.com)
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
int bestTeamScore(vector<int> &scores, vector<int> &ages)
{
int n = scores.size();
vector<pair<int, int>> a;
vector<int> dp(n, 0);
for (int i = 0; i < n; ++i)
{
a.push_back({ages[i], scores[i]});
}
sort(a.begin(), a.end());
dp[0] = a[0].second;
int ans = dp[0];
for (int i = 1; i < n; ++i)
{
dp[i] = a[i].second;
for (int j = 0; j < i; ++j)
{
if (a[i].second >= a[j].second)
{
dp[i] = max(dp[i], dp[j] + a[i].second);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
vector<int> c;
int query(int pos)
{
int ans = 0;
while (pos >= 1)
{
ans = max(ans, c[pos]);
pos -= lowbit(pos);
}
return ans;
}
void add(int pos, int k, int n)
{
while (pos <= n)
{
c[pos] = max(c[pos], k);
pos += lowbit(pos);
}
}
int lowbit(int x)
{
return x & -x;
}
int bestTeamScore(vector<int> &scores, vector<int> &ages)
{
int n = scores.size();
vector<pair<int, int>> a;
vector<int> dp(n, 0);
int max_age = 0;
for (int i = 0; i < n; ++i)
{
a.push_back({scores[i], ages[i]});
max_age = max(ages[i], max_age);
}
c.resize(max_age + 1, 0);
sort(a.begin(), a.end());
int ans = 0;
for (int i = 0; i < n; ++i)
{
dp[i] = query(a[i].second) + a[i].first;
add(a[i].second, dp[i], max_age);
ans = max(ans, dp[i]);
}
return ans;
}
};
|