首页 > 其他分享 >251 麦当劳

251 麦当劳

时间:2024-11-08 12:18:54浏览次数:3  
标签:int currst 样例 麦当劳 天中 251

// 704 麦当劳.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
http://oj.daimayuan.top/course/5/problem/251


喜欢吃麦当劳的蜗蜗要在学校呆 n
 天,如果第 i
 天蜗蜗吃到了麦当劳,他可以获得 ai
 点快乐值。然而蜗蜗不能吃太多麦当劳,在连续的 m
 天中,他最多只能有一半的天数吃麦当劳。请问蜗蜗在这 n
 天中最多可以得到多少快乐值?

输入格式
第一行两个整数 n,m。

第二行 n 个整数 a1,a2,...,an。

输出格式
一行一个整数表示答案。

样例输入
4 3
1 2 9 4
样例输出
5
数据范围
对于 100%
 的数据,保证 2≤n≤100000,2≤m≤8,1≤ai≤10000


8 8
6808 5250 74 3659 8931 1273 7545 879



*/

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>


using namespace std;

const int N = 100010;
int a[N];
long long pre[1 << 8];
long long curr[1 << 8];
int n, m;


bool check(int st) {
	int cnt = 0;
	while (st) {
		if (st & 1) cnt++;
		st >>= 1;
	}
	if (cnt <= m / 2) return true;
	return false;
}



int main()
{
	cin >> n >> m;

	for (int i = 1; i <= n; i++) cin >> a[i];

	for (int i = 0; i < (1<<8); i++) {
		pre[i]  = -999999999999999;
		curr[i] = -999999999999999;
	}
	
	pre[0] = 0;
	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		int f = 0;
		for (int st = 0; st <( 1 << m); st++) {
			int currst = st / 2;
			if(pre[st]>=0)
				curr[currst] = max(pre[st] , curr[currst]);
			if (check(currst + (1 <<  (m-1)))  ) {
				curr[currst + (1 << (m-1))] = max(curr[currst + (1 << (m - 1))], pre[st] + a[i]);
			}
			if(i==n)
				ans =max(ans, max(curr[currst], curr[currst + (1 << (m - 1))]));
		}
		swap(pre,curr);
	}

	cout << ans << endl;
	

	return 0;
}

标签:int,currst,样例,麦当劳,天中,251
From: https://www.cnblogs.com/itdef/p/18534833

相关文章

  • 《使用Gin框架构建分布式应用》阅读笔记:p251-p271
    《用Gin框架构建分布式应用》学习第14天,p251-p271总结,总21页。一、技术总结1.Docker&DockerComposeversion:"3.9"services:api:image:apienvironment:-MONGO_URI=mongodb://admin:password@mongodb:27017/test?authSource=admin&readPreference=p......
  • P2251 质量检测
    题目大意给定长度为\(N\)的数组\(A\),定义数组\(Q\),\(Q_i=\min{\{A_1,A_2,\cdots,A_i\}}\)。对于每个\(i\left(1\lei\leN-M+1\right)\),输出\(Q_{i}\),\(M\)是给定的常数。样例输入104165695131420812输出5555588解决方法发现题目是要获取每......
  • jsp高校学生综合评测系统e9251--程序+源码+数据库+调试部署+开发环境
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表学生用户,管理老师,上传中心,测评结果,学生素质,综合成绩开题报告内容一、课题背景随着高等教育的发展,高校学生综合评测已成为衡量学生综合素质、促进教学改革......
  • KBJ2510-ASEMI整流桥KBJ2510参数、封装、尺寸
    编辑:llKBJ2510-ASEMI整流桥KBJ2510参数、封装、尺寸型号:KBJ2510品牌:ASEMI封装:KBJ-4批号:2024+现货:50000+最大重复峰值反向电压:1000V最大正向平均整流电流(Vdss):25A功率(Pd):大功率芯片个数:4引脚数量:4安装方式:插件类型:插件桥堆、整流桥正向浪涌电流IFSM:350A正向电压:1.......
  • GBJ2510-ASEMI整流桥GBJ2510参数、封装、尺寸
    编辑:llGBJ2510-ASEMI整流桥GBJ2510参数、封装、尺寸型号:GBJ2510品牌:ASEMI封装:GBJ-4安装方式:直插批号:2024+现货:50000+正向电流(Id):25A反向耐压(VRRM):1000V正向浪涌电流:350A正向电压(VF):1.10V引脚数量:4芯片个数:4芯片尺寸:MIL功率(Pd):中小功率工作温度:-55°C~150°C类型:整......
  • JAVA宠物用品网络商城的设计与实现2516源码论文
    JAVA宠物用品网络商城的设计与实现2516源码论文摘要随着生活和工作方面的压力逐渐增加,人们对宠物的依赖和需求也就变得越来越大。宠物用品商城是一个能使得繁忙的或者不喜欢出门的人,足不出户而又很方便地购得宠物的日用品,这样也不会影响到工作或者浪费了休息的时间。如今......
  • Newtec MDM2510 REST API
    NewtecMDM2510RESTAPI SatOct1214:37:112024<--L10SatOct1214:37:112024<--A15SatOct1214:37:112024<--W15SatOct1214:37:112024<--S172.0000000.0000000.000000SatOct1214:37:112024......
  • oracle 19c dgbroker 报错ORA-16664 with ORA-12514如何解决
    alert中一堆这个保存一新***********************************************************************FatalNIconnecterror12504,connectingto:(DESCRIPTION=(CONNECT_DATA=(SERVICE_NAME=)(INSTANCE_NAME=hrz)(CID=(PROGRAM=oracle)(HOST=sd4)(USER=oracle)))(ADDRESS......
  • 洛谷P2513 逆序对数列
    Problem给定n,k,求得1~n中有多少种排列使得逆序对个数为k?(n,k<=1000)Solve考虑DP:设f[i][j]为i个数中逆序对数量为j的排列数量但因为我们并不知道我们这i个数到底是谁,难以通过以前的状态得到设f[i][j]为将i放入之前的排列后,逆序对数量为k的排列数此时我们发现可以确定前i-1......
  • FINANCE 251: Financial Management
    FINANCE 251: Financial Management2024 Semester 2 (1245)Assignment PART 1Instructions:This isaGroupassignment(Part 1) which also includes an Individual component (Part 2). You mustform.yourowngroups (min 2, max5 people per......