#1044 : 状态压缩·一

2024-01-25 10:32
文章标签 压缩 状态 1044

本文主要是介绍#1044 : 状态压缩·一,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

时间限制: 10000ms
单点时限: 1000ms
内存限制: 256MB
描述

小Hi和小Ho在兑换到了喜欢的奖品之后,便继续起了他们的美国之行,思来想去,他们决定乘坐火车前往下一座城市——那座城市即将举行美食节!

但是不幸的是,小Hi和小Ho并没有能够买到很好的火车票——他们只能够乘坐最为破旧的火车进行他们的旅程。

不仅如此,因为美食节的吸引,许多人纷纷踏上了和小Hi小Ho一样的旅程,于是有相当多的人遭遇到了和小Hi小Ho一样的情况——这导致这辆车上的人非常非常的多,以至于都没有足够的位置能让每一个人都有地方坐下来。

小Hi和小Ho本着礼让他们的心情——当然还因为本来他们买的就是站票,老老实实的呆在两节车厢的结合处。他们本以为就能够这样安稳抵达目的地,但事与愿违,他们这节车厢的乘务员是一个强迫症,每隔一小会总是要清扫一次卫生,而时值深夜,大家都早已入睡,这种行为总是会惊醒一些人。而一旦相邻的一些乘客被惊醒了大多数的话,就会同乘务员吵起来,弄得大家都睡不好。

将这一切看在眼里的小Hi与小Ho决定利用他们的算法知识,来帮助这个有着强迫症的乘务员——在不与乘客吵起来的前提下尽可能多的清扫垃圾。

小Hi和小Ho所处的车厢可以被抽象成连成一列的N个位置,按顺序分别编号为1..N,每个位置上都有且仅有一名乘客在休息。同时每个位置上都有一些垃圾需要被清理,其中第i个位置的垃圾数量为Wi。乘务员可以选择其中一些位置进行清理,但是值得注意的是,一旦有编号连续的M个位置中有超过Q个的位置都在这一次清理中被选中的话(即这M个位置上的乘客有至少Q+1个被惊醒了),就会发生令人不愉快的口角。而小Hi和小Ho的任务是,计算选择哪些位置进行清理,在不发生口角的情况下,清扫尽可能多的垃圾。

提示一:无论是什么动态规划,都需要一个状态转移方程!

提示二:好像什么不对劲?状态压缩哪里去了?

输入

每个测试点(输入文件)有且仅有一组测试数据。

每组测试数据的第一行为三个正整数N、M和Q,意义如前文所述。

每组测试数据的第二行为N个整数,分别为W1到WN,代表每一个位置上的垃圾数目。

对于100%的数据,满足N<=1000, 2<=M<=10,1<=Q<=M, Wi<=100

输出

对于每组测试数据,输出一个整数Ans,表示在不发生口角的情况下,乘务员最多可以清扫的垃圾数目。

样例输入
5 2 1
36 9 80 69 85 
样例输出
201
经典状态压缩,注重思路。代码注释部分好好理解
#include <iostream>
#include <string.h>
#include <cstdio>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <math.h>
using namespace std;
#define pow2(x) ((1<<(x)))
int f[1005][1100];
int value[1005];
int cal(int num)
{int ans=num&1;while(num!=0){num=num/2;if(num&1==1)ans++;}return ans;
}
int main()
{int n,m,q;while(~scanf("%d%d%d",&n,&m,&q)){for(int i=1;i<=n;i++){scanf("%d",&value[i]);}int tem=pow2(m)-1;memset(f,0,sizeof(f));int ttt;ttt=pow2(m-1);for(int i=0;i<n;i++){for(int j=0;j<=pow2(m)-1;j++){if(cal(j/2)<q)//能继续添加就添加或不添加{f[i+1][(j/2)+ttt]=max(f[i+1][(j/2)+ttt],f[i][j]+value[i+1]);f[i+1][(j/2)]=max(f[i][j],f[i+1][(j/2)]);}else//不能继续添加f[i+1][(j/2)]=max(f[i][j],f[i+1][(j/2)]);}}int aa=0;for(int j=0;j<=tem;j++){aa=max(aa,f[n][j]);}printf("%d\n",aa);}
}



这篇关于#1044 : 状态压缩·一的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/642993

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

hdu1565(状态压缩)

本人第一道ac的状态压缩dp,这题的数据非常水,很容易过 题意:在n*n的矩阵中选数字使得不存在任意两个数字相邻,求最大值 解题思路: 一、因为在1<<20中有很多状态是无效的,所以第一步是选择有效状态,存到cnt[]数组中 二、dp[i][j]表示到第i行的状态cnt[j]所能得到的最大值,状态转移方程dp[i][j] = max(dp[i][j],dp[i-1][k]) ,其中k满足c

状态dp总结

zoj 3631  N 个数中选若干数和(只能选一次)<=M 的最大值 const int Max_N = 38 ;int a[1<<16] , b[1<<16] , x[Max_N] , e[Max_N] ;void GetNum(int g[] , int n , int s[] , int &m){ int i , j , t ;m = 0 ;for(i = 0 ;

hdu3006状态dp

给你n个集合。集合中均为数字且数字的范围在[1,m]内。m<=14。现在问用这些集合能组成多少个集合自己本身也算。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.Inp

从状态管理到性能优化:全面解析 Android Compose

文章目录 引言一、Android Compose基本概念1.1 什么是Android Compose?1.2 Compose的优势1.3 如何在项目中使用Compose 二、Compose中的状态管理2.1 状态管理的重要性2.2 Compose中的状态和数据流2.3 使用State和MutableState处理状态2.4 通过ViewModel进行状态管理 三、Compose中的列表和滚动

实例:如何统计当前主机的连接状态和连接数

统计当前主机的连接状态和连接数 在 Linux 中,可使用 ss 命令来查看主机的网络连接状态。以下是统计当前主机连接状态和连接主机数量的具体操作。 1. 统计当前主机的连接状态 使用 ss 命令结合 grep、cut、sort 和 uniq 命令来统计当前主机的 TCP 连接状态。 ss -nta | grep -v '^State' | cut -d " " -f 1 | sort |

状态模式state

学习笔记,原文链接 https://refactoringguru.cn/design-patterns/state 在一个对象的内部状态变化时改变其行为, 使其看上去就像改变了自身所属的类一样。 在状态模式中,player.getState()获取的是player的当前状态,通常是一个实现了状态接口的对象。 onPlay()是状态模式中定义的一个方法,不同状态下(例如“正在播放”、“暂停

qml states 状态

states 状态 在QML中,states用于定义对象在不同状态下的属性变化。每个状态可以包含一组属性设置,当状态改变时,这些属性设置会被应用到对象上。 import QtQuick 2.15import QtQuick.Controls 2.15// 定义应用程序的主窗口ApplicationWindow {visible: true // 使窗口可见width: 640 /

通用内存快照裁剪压缩库Tailor介绍及源码分析(一)

背景 我们知道内存快照是治理 OOM 问题及其他类型的内存问题的重要数据源,内存快照中保存了进程虚拟机的完整的堆内存数据,很多时候也是调查其他类型异常的重要参考。但是dump出来的堆转储文件.hprof往往很大,以 LargeHeap 应用为例,其 OOM 时的内存快照大小通常在512M左右,要有效的存储和获取都是一个问题。 线下拿到hprof文件相对容易,也可以预防OOM,但覆盖的场景十分有

[轻笔记] ubuntu Shell脚本实现监视指定进程的运行状态,并能在程序崩溃后重启动该程序

根据网上博客实现,发现只能监测进程离线,然后对其进行重启;然而,脚本无法打印程序正常状态的信息。自己通过不断修改测试,发现问题主要在重启程序的命令上(需要让重启的程序在后台运行,不然会影响监视脚本进程,使其无法正常工作)。具体程序如下: #!/bin/bashwhile [ 1 ] ; dosleep 3if [ $(ps -ef|grep exe_name|grep -v grep|