【LGR-161-Div.3】洛谷基础赛 #4 P9688 Colo.

这篇具有很好参考价值的文章主要介绍了【LGR-161-Div.3】洛谷基础赛 #4 P9688 Colo.。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

原题链接:P9688 Colo.

很显然,能够共存的颜色一定不会相交,所以可以记录每个颜色最左边的位置和最右边的位置,我们对于每个颜色只考虑,这个颜色左边的可以和这个颜色共存的额颜色
用f[i][j]表示当前考虑i这种颜色,选i这种颜色,然后在i这种颜色之前(包括这种颜色)一共选了j种颜色的最大价值
那么很显然,我们可以枚举i这种颜色左边的可以和i共存的颜色,用k代表,依次取不选k和选了k再选i的最大值,最终再取最大值

也就是,对于每一个j,我们都做一遍dp(i,j)=max(dp(j,j−1)+w[i],dp(i,j))

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int maxn = 10020;

int a[maxn];              //存储序列
int l[maxn], r[maxn];     //l[i]记录i这种颜色最左边的位置,r[i]记录i这种颜色最右边的位置

int w[maxn];              //w[i]存储i这种颜色的价值

int f[maxn][maxn];        //f[i][j]表示的是选择i这种颜色,并且一共学了j种颜色的最大价值
//那么我们考虑所有可以和i这种颜色一块保留的颜色并放到i前面的,例如jk,比较保留jk和不保留jk的结果
//也就是f[i][j]=max(f[i][j],f[i][j-1]+w[jk])

int n, k;

vector<int>e[maxn];



signed main()
{
    cin >> n >> k;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (!l[a[i]])l[a[i]] = i;           //如果这种颜色的最左边位置还为0,那么此时就是它的最左边位置
        r[a[i]] = i;                        //不断更新这种颜色的最右边
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
    }


    for (int i = 0; i <= n; i++) {
        for (int j = 1; j <= k; j++)f[i][j] = -1e18;                     //这里的初始化之所以i从0开始,j从1开始,是为了让f[i][0]=0,再加上后面e[a[i]].push_back(0);可以保证,第一次执行
                                                                         /*
                                                                                  for (int p = 1; p <= k; p++) {
                                                                                        f[a[i]][p] = max(f[a[i]][p], f[v][p - 1] + w[a[i]]);
                                                                                     }
                                                                                可以把f[a[i][1]设置成w[a[i]]
                                                                          */
    }

    for (int i = 1; i <= n; i++) {
        e[a[i]].push_back(0);
        for (int j = 1; j <= n; j++) {
            if (i == j)continue;
            if (r[a[j]]<l[a[i]] && a[i]>a[j])e[a[i]].push_back(a[j]);//,cout<<a[i]<<" "<<a[j]<<endl;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < e[a[i]].size(); j++) {
            int v = e[a[i]][j];
            for (int p = 1; p <= k; p++) {
                f[a[i]][p] = max(f[a[i]][p], f[v][p - 1] + w[a[i]]);
            }
        }
    }
   
    int mx = -1;
    for (int i = 1; i <= n; i++)mx = max(mx, f[i][k]);
    cout << mx;
    return 0;
}


文章来源地址https://www.toymoban.com/news/detail-741844.html

到了这里,关于【LGR-161-Div.3】洛谷基础赛 #4 P9688 Colo.的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Educational Codeforces Round 161 (Rated for Div. 2) E题 动态规划逼近,二进制拆分补充,注意严格递增strictly increasing

    Problem - E - Codeforces 目录 推荐视频: 题意: 细节(我踩得没什么价值的坑): 思路: 对样例3 (X = 13)做解释: —————— 总思路: —————— 动态规划逼近: —————— 二进制拆分补充剩余: 核心代码:  E_哔哩哔哩_bilibili 其实有一些细节说的不是特别清楚好

    2024年01月24日
    浏览(42)
  • [4G/5G/6G专题基础-161]:常见的滤波技术

    滤波(Filtering)是信号处理中的一种基本操作,用于改变信号的特性或者 去除信号中的干扰成分 。滤波器可以看作是一种系统,将输入信号作为输入,经过处理后产生输出信号。 滤波在信号处理中广泛应用,用于 去除噪声 、 平滑信号 、 频率选择 等。 不同的滤波器类型和

    2024年02月13日
    浏览(51)
  • 2--DIV CSS基础

    CSS指的是层叠样式表(Cascading Style Sheets),也称级联样式表,是一种用来表现HTML(标准通用标记语言的一个应用)或XML(标准通用标记语言的一个子集)等文件样式的计算机语言。CSS描述了如何在屏幕、纸张或其他媒体上显示HTML元素,可以同时控制多张网页的布局。 DIV是

    2024年02月16日
    浏览(32)
  • leetcode原题: 峰与谷

    题目: 在一个整数数组中,“峰”是大于或等于相邻整数的元素,相应地,“谷”是小于或等于相邻整数的元素。例如,在数组{5, 8, 4, 2, 3, 4, 6}中,{8, 6}是峰, {5, 2}是谷。现在给定一个整数数组,将该数组按峰与谷的交替顺序排序。 示例: 输入: [5, 3, 1, 2, 3] 输出: [5, 1, 3,

    2024年02月11日
    浏览(54)
  • leetcode原题:节点间通路

    题目: 给定有向图,设计一个算法,找出两个节点之间是否存在一条路径。 示例:  输入:n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2  输出:true  解题思路: 本题借助队列,利用队列的先进先出的特点,保证访问每个节点的顺序不被破坏。 1. 建立邻接表map ,讲

    2024年02月13日
    浏览(51)
  • leetcode原题: 生存人数

    题目: 给定 N 个人的出生年份和死亡年份,第 i 个人的出生年份为 birth[i] ,死亡年份为 death[i] ,实现一个方法以计算生存人数最多的年份。 你可以假设所有人都出生于 1900 年至 2000 年(含 1900 和 2000 )之间。如果一个人在某一年的任意时期处于生存状态,那么他应该被纳入

    2024年02月10日
    浏览(46)
  • leetcode原题:变位词组(哈希)

    题目: 编写一种方法,对字符串数组进行排序,将所有变位词组合在一起。变位词是指字母相同,但排列不同的字符串。 示例: 输入: [\\\"eat\\\", \\\"tea\\\", \\\"tan\\\", \\\"ate\\\", \\\"nat\\\", \\\"bat\\\"], 输出: [   [\\\"ate\\\",\\\"eat\\\",\\\"tea\\\"],   [\\\"nat\\\",\\\"tan\\\"],   [\\\"bat\\\"] ] 解题思路: 本题是需要将相同的变位词放在一维数组中,

    2024年02月11日
    浏览(37)
  • leetcode原题:绘制直线(位运算)

    题目: 已知一个由像素点组成的单色屏幕,每行均有 w 个像素点,所有像素点初始为 0 ,左上角位置为 (0,0) 。 现将每行的像素点按照「每 32 个像素点」为一组存放在一个 int 中,再依次存入长度为 length 的一维数组中。 我们将在屏幕上绘制一条从点 (x1,y) 到点 (x2,y) 的直线(

    2024年02月12日
    浏览(38)
  • 计算机网络——习题——书上原题

    目录 第一章 1. 填空题 第二章 1. 填空题 第三章 1. 填空题 2.选择题 第四章 1. 填空题 第五章 第六章 1. 填空题 (1)计算机网络的主要功能包括 资源共享、数据通信、分布式处理、提高计算机的可靠性和集中管理 。 (2)常用的网络传输介质为 有线 和 无线 两种。其中,有线

    2024年02月03日
    浏览(34)
  • leetcode原题: 堆箱子(动态规划实现)

    题目: 给你一堆n个箱子,箱子宽 wi、深 di、高 hi。箱子不能翻转,将箱子堆起来时,下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法,搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。 输入使用数组 [wi, di, hi] 表示每个箱子。 示例:  输入:box

    2024年02月11日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包