17蓝桥杯决赛对局匹配-程序员宅基地

技术标签：蓝桥杯

dp问题

先转换为权值数据，把权值数据化为K组（K1，K2……）数据
每一组数据相当于k等于1的子问题。
最后将最后k个加起来就是答案。
比如说样例
21 2
1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6
转化为权值数据为1 2 3 4 5 6
分成两组
1 3 5 k1
2 4 6 k2
k1子问题的答案是1+5=6
k2子问题的答案是2+6=8

最后问题的答案就是14。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,k;
const int MAX = 100010;
int dp[MAX]={0};
int ans[MAX]={0};
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)//赋权值 
	{
		int buf;
		scanf("%d",&buf);
		ans[buf]++;
	}
	for(int i=0;i<=MAX;i++)//实际上是进行了k次dp，这里简写成一趟。 
	{
		int buf1,buf2;
		if(i-k<0)buf1=0; 
		else buf1=dp[i-k];
		
		if(i-2*k<0)buf2=0;
		else buf2=dp[i-2*k];
		
		dp[i]=max(buf1,buf2+ans[i]);//状态转移方程 
	}
	if(k==0)//特判一下k=0的情况 
	{
        int Count=0;
        for(int i=1;i<=MAX;i++)
            if(ans[i]!=0)
                Count++;
        printf("%d",Count);
    }
    else{
    	int tot=0;
		for(int i=0;i<k;i++)//将后面k个加起来就是答案 
			tot+=dp[MAX-i];
		printf("%d\n",tot);
    }
	for(int i = 0;i<100;i++)
		printf("%d ",dp[i]); 
	return 0;
}

本文链接：https://blog.csdn.net/qq_39099462/article/details/79965021

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

EasyDarwin开源流媒体云平台之EasyRMS录播服务器功能设计_开源录播系统-程序员宅基地

文章浏览阅读3.6k次。需求背景EasyDarwin开发团队维护EasyDarwin开源流媒体服务器也已经很多年了，之前也陆陆续续尝试过很多种服务端录像的方案，有：在EasyDarwin中直接解析收到的RTP包，重新组包录像；也有：在EasyDarwin中新增一个RecordModule，再以RTSPClient的方式请求127.0.0.1自己的直播流录像，但这些始终都没有成气候；我们的想法是能够让整套EasyDarwin_开源录播系统

oracle Plsql 执行update或者delete时卡死问题解决办法_oracle delete update 锁表问题-程序员宅基地

文章浏览阅读1.1w次。今天碰到一个执行语句等了半天没有执行：delete table XXX where ......,但是在select 的时候没问题。后来发现是在执行select * from XXX for update 的时候没有commit，oracle将该记录锁住了。可以通过以下办法解决：先查询锁定记录 Sql代码 SELECT s.sid, s.seri_oracle delete update 锁表问题

Xcode Undefined symbols 错误_xcode undefined symbols:-程序员宅基地

文章浏览阅读3.4k次。报错信息error:Undefined symbol: typeinfo for sdk::IConfigUndefined symbol: vtable for sdk::IConfig具体信息：Undefined symbols for architecture x86_64: "typeinfo for sdk::IConfig", referenced from: typeinfo for sdk::ConfigImpl in sdk.a(config_impl.o) _xcode undefined symbols:

项目05(Mysql升级07Mysql5.7.32升级到Mysql8.0.22)_mysql8.0.26 升级32-程序员宅基地

文章浏览阅读249次。背景《承接上文,项目05(Mysql升级06Mysql5.6.51升级到Mysql5.7.32)》,写在前面需要(考虑)检查和测试的层面很多，不限于以下内容。参考文档https://dev.mysql.com/doc/refman/8.0/en/upgrade-prerequisites.htmllink推荐阅读以上链接，因为对应以下问题，有详细的建议。官方文档：不得存在以下问题：0.不得有使用过时数据类型或功能的表。不支持就地升级到MySQL 8.0，如果表包含在预5.6.4格_mysql8.0.26 升级32

高通编译8155源码环境搭建_高通8155 qnx 源码-程序员宅基地

文章浏览阅读3.7k次。一.安装基本环境工具：1.安装git工具sudo apt install wget g++ git2.检查并安装java等环境工具2.1、执行下面安装命令#!/bin/bashsudoapt-get-yinstall--upgraderarunrarsudoapt-get-yinstall--upgradepython-pippython3-pip#aliyunsudoapt-get-yinstall--upgradeopenjdk..._高通8155 qnx 源码

firebase 与谷歌_Firebase的好与不好-程序员宅基地

文章浏览阅读461次。firebase 与谷歌大多数开发人员都听说过Google的Firebase产品。这就是Google所说的“ 移动平台，可帮助您快速开发高质量的应用程序并发展业务。 ”。它基本上是大多数开发人员在构建应用程序时所需的一组工具。在本文中，我将介绍这些工具，并指出您选择使用Firebase时需要了解的所有内容。在开始之前，我需要说的是，我不会详细介绍Firebase提供的所有工具。我..._firsebase 与 google