背包

谁在说谎

https://ac.nowcoder.com/acm/contest/1168/H

转化为 求最大不重合区间权值和的问题 就非常直观了。

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define x first
#define y second
map<int, int> mp[N];
int n, a, b;
int dp[N];  //最大
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a, &b);  // a个人比他高 b个人比他低
        if (a + b > n) continue;
        mp[b][n - a]++;  // n-a :不高于他的人数 也就是说,n-a=b+同分人数
    }
    for (int i = 0; i < n; i++) {
        for (auto it : mp[i])
            dp[it.x] = max(dp[it.x],              //可以放弃这个区间
                           dp[i] + min(it.x - i,  //同分的容纳上限n-a-b
                                       it.y));    //有多少个报了这个的
        dp[i + 1] = max(dp[i + 1], dp[i]);        //可以放弃这个区间
    }
    printf("%d\n", n - dp[n]);
    return 0;
}
算法竞赛之路 文章被收录于专栏

整理、记录算法竞赛的好题

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像 头像
点赞 评论 收藏
转发
头像
2022-12-23 19:49
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
02-01 22:09
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议