首页 > 其他分享 >[花店橱窗布置]

[花店橱窗布置]

时间:2024-04-11 09:00:30浏览次数:17  
标签:花店 橱窗 mpos 线段 tree pos maxn dp 布置

花店橱窗布置

题目大意

在保持顺序的情况下,求摆放的最大美学值

做法

正常做法来说是dp,设dp[i][j]表示第i束花放不放在第j个花盆里的最大值,转移方程就应该是:

不放:$$dp[i][j]=dp[i][j-1]$$

放:$$dp[i][j]=dp[i-1][j-1]+a[i]$$

但是当时突发奇想,想了个线段树,没想到写过了,故来记录线段树做法,那么为什么可以用线段树做呢,可以发现, 下一层更新答案要在上一层的基础上再往下更新,第i束花最前可以放在第i个花盆(题意),那么\(f[i][j]\)表示第i束花放在第j个花盆的最大值,那么他一定是由\(max(f[i-1][i-1...j-1])\)更新来的,看到这个方程第一眼想到了单调队列去维护,但发现这个长度不是固定的,所以不能用这个来维护,那么还能动态维护区间最大值的方式就想到了线段树。把原来线段树维护的\(sum\)改成维护\(max\)可行,因为每一层都只跟上一层有关,所以线段树只需要维护上一层的信息就可以,而又因为\(f[i][]\)只跟\(f[i-1][]\)有关,故线段树相当于那个压成一维的滚动数组,更新就要倒着更新。\(dp是O(nm)的复杂度,线段树维护只多了一个log(m),故是O(nmlogm)的复杂度,可以过全部数据\)

洛谷P1854

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 105,inf = 2147483647;
int n,m,f[maxn][maxn],a[maxn][maxn],res,pos,pre[maxn][maxn],ans[maxn];

struct Tree{
	int l,r,k,maxi,pos;
}tree[maxn<<2];

void build(int l,int r,int k)
{
	tree[k] = (Tree){l,r,k,0};
	if(l == r)
	{
		tree[k].maxi = a[1][l];
		tree[k].pos = l;
		return ;
	}
	int mid = l + r >> 1;
	build(l,mid,k<<1);
	build(mid+1,r,(k<<1)+1);
	if(tree[k<<1].maxi >= tree[(k<<1)+1].maxi)
	{
		tree[k].maxi = tree[k<<1].maxi;
		tree[k].pos = tree[k<<1].pos;
	}
	else{
		tree[k].maxi = tree[(k<<1)+1].maxi;
		tree[k].pos = tree[(k<<1)+1].pos;
	}
	return ; 
}

void update(int p,int v,int k)
{
	if(tree[k].l == tree[k].r)
	{
		tree[k].maxi = v;
		return ;
	}
	int mid = tree[k].l + tree[k].r >> 1;
	if(p <= mid)
		update(p,v,k<<1);
	else update(p,v,(k<<1)+1);
	if(tree[k<<1].maxi >= tree[(k<<1)+1].maxi)
	{
		tree[k].maxi = tree[k<<1].maxi;
		tree[k].pos = tree[k<<1].pos;
	}
	else{
		tree[k].maxi = tree[(k<<1)+1].maxi;
		tree[k].pos = tree[(k<<1)+1].pos;
	}
	return ;
}

void query(int l,int r,int k)
{
	if(tree[k].l >= l && tree[k].r <= r)
	{
		if(tree[k].maxi >= res)
		{
			res = tree[k].maxi;
			pos = tree[k].pos;
		}
		return ;
	}
	int mid = (tree[k].l + tree[k].r) >> 1;
	if(l <= mid)
		query(l,r,k<<1);
	if(r > mid)
		query(l,r,(k<<1)+1);
	return ;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	build(1,m,1);
	for(int i=2;i<=n;i++)
	{
		for(int j=m;j>=1;j--)
		{
			if(j >= i)//最前要在第i位
			{
				res = -inf;
				query(i-1,j-1,1);//查询i-1到j-1的最大值
				f[i][j] = res + a[i][j];//更新答案
				pre[i][j] = pos;//记录f[i][j]是由上一层的哪个更新而来
				update(j,f[i][j],1);//同时修改线段树中的值
			}
			else update(j,-inf,1);//前面的更新为负无穷,这样不会影响答案
		}
	}
	printf("%d\n",tree[1].maxi);//最终答案肯定是f[n][n...m]中的最大值,
	int k = n,mpos = tree[1].pos,cnt = 0;
	ans[++cnt] = mpos;
	while(pre[k][mpos])
	{
		ans[++cnt] = pre[k][mpos];
		mpos = pre[k][mpos];
		k --;
	}
	for(int i=cnt;i>=1;i--)
		printf("%d ",ans[i]);
	return 0;
}

标签:花店,橱窗,mpos,线段,tree,pos,maxn,dp,布置
From: https://www.cnblogs.com/-Wind-/p/18127951

相关文章

  • Memcache分布式布置方案--一致性Hash分布机制PHP实现
    一致性Hash分布简介在服务器数量不发生改变时,普通的Hash分布可以很好地运作。当服务器的数量发生改变时,问题就出来了,试想,增加一台服务器时,同一个key经过Hash之后,与服务器取模的结果跟没增加服务器之前的结果会不一样,这就导致之前保存的数据丢失。为了把丢失的数据减少到最少,可以采......
  • 【附源码】JAVA计算机毕业设计网上花店系统(源码+mysql+文档)
    本系统(程序+源码)带文档lw万字以上  文末可领取本课题的JAVA源码参考系统程序文件列表系统的选题背景和意义选题背景:随着互联网技术的飞速发展,电子商务已经成为现代社会中一个重要的商业活动形式。网络购物作为电子商务的重要组成部分,以其方便快捷的特点深受广大消费者......
  • 三八妇女节智慧花店/自动售花机远程视频智能监控解决方案
    一、项目背景国家统计局发布的2023年中国经济年报显示,全年社会消费品零售总额471495亿元,比上年增长7.2%。我国无人零售整体发展迅速,2014年市场规模约为17亿元。无人零售自助终端设备市场规模超过500亿元,年均复合增长率超50%。从落地形式来看,无人零售发展至今覆盖的品类越来越多,但......
  • 花店橱窗(线性DP)
    线性DP——花店橱窗谨以此题解献给线性dp最后一道题题目大致Descriptionxq和他的老婆xz最近开了一家花店,他们准备把店里最好看的花都摆在橱窗里。但是他们有很多花瓶,每个花瓶都具有各自的特点,因此,当各个花瓶中放入不同的花束时,会产生不同的美学效果。为了使橱窗里的花摆放的最......
  • 水电布置
    1.烟机插座排在吊顶内。2.台面上插座H=1100mm3,冰箱插座H:600nmm,也可在侧面。4,水槽柜出水H=400mm,插座H=500mm,水槽柜内插座备3个,至少也要备2个。5.排水口离墙深度200mm以内,走地排,下水管走地柜下走的,水管最高处离地砖高度不超过110mm,从后面走要贴墙走,保障后期使用与维修请在橱柜安装......
  • 【送酒小程序系统源码】/花店送花系统/蛋糕店系统/奶茶店系统源码
    前端uniapp+后端thinkphp+数据库mysql多门店外卖餐饮点餐系统预约点餐匹配附近店铺 堂食外卖带走  菜品管理.根据用户的位置匹配附近饭店 点餐后,可以在线等叫号餐时输入手机号并支付后,可以支持外支持多规格、备注等快捷功能,以吸多多门店管理 数据概览支持微信小程序 ......
  • beego框架 golang web框架-网上花店
    beego框架golangweb框架-网上花店beego网上花店功能介绍主页商品列表展示商品详情用户登录注册购买购物车评价用户中心订单列表后台管理页商品管理添加修改删除商品用户管理添加删除用户网上花店功能比较简单适合刚接触beego的初学者使用技术beego框架My......
  • 【题解】Luogu[P7706] 「Wdsr-2.7」文文的摄影布置
    Link一道很有意思的线段树题。第一步分析,我们要求最大的\(a_i+a_k-\min{(b_j)}\),事实上我们可以直接省去这个\(\min\)因为要最大化这个东西,选出来的\(b_j\)必然是最小的,所以原题转化为给定\(l,r\)求\(\max{(a_i-b_j+a_k)}\)其中\(i<j<k\)。第二步分析,我们发现这是一......
  • IP新地标!三思1700㎡“裸眼3D悬浮橱窗”惊艳深圳湾区之心
    适逢炎炎夏日,当你走在街头,看见一瓶悬浮半空的巨型雪碧,是否会想起昔日“望梅止渴”的故事?是的!这样一幕酷炫的现代版场景近期就在深圳南山区上演。图片来源:深圳南山区电信大厦三思LED屏无论是南海大道来往深南大道、滨海大道,抑或是前往蛇口、前海片区的主要交通干道。在这条东西向交......
  • 脚本组件界面布置
    脚本组件界面布置usingUnityEngine;publicclassJuse:MonoBehaviour{[Header("TypeOne")]//标题组名publicHusedis;publicGameObjectcia;publicGameObjectdia;[Space(50)]//两行之间间隙大小publicintdes;[Tooltip("Thisis......