首页 > 其他分享 >P8548小挖的买花(01背包双重限制之限制一个最大一个最小)

P8548小挖的买花(01背包双重限制之限制一个最大一个最小)

时间:2023-01-12 22:13:16浏览次数:70  
标签:fr 01 P8548 int 买花 leq cost 枝花 dp

P8548小挖的买花(双重限制之限制一个最大一个最小)

MarkDown崩了我太菜不会改,大家还是去洛谷看原题吧

题目传送门:小挖的买花

题目背景

小挖喜欢买花,但是 ta 太懒了!所以这个任务全权交给了你。

题目描述

花店里只有 $n$ 株花,每一株花都有三个属性:价格 $cost_i$、美丽度 $be_i$、新鲜程度 $fr_i$。

小挖每次都有不同的要求。准确来说,对于第 $j$ 次买花,你手里的钱至多能买下总价为 $c_j$ 的花。同时,小挖还要求购买花的新鲜程度总和大于等于 $f_j$。而小挖希望知道,在满足 ta 给出的条件后,购买花的美丽度总和的最大值是多少?

小挖一共要让你买 $q$ 次花,你能否正确回答 ta 的问题呢?询问彼此独立。

输入格式

第 $1$ 行,共两个正整数 $n,q$。

第 $2\sim n+1$ 行,每行三个正整数 $cost_i,fr_i,be_i$,分别表示一株花的三个属性。

第 $n+2\sim n+q+1$ 行,每行两个正整数 $c_j,f_j$,表示每次买花时的要求。

输出格式

共 $q$ 行,每行一个整数,表示美丽度总和的最大值。

样例 #1

样例输入 #1

5 1
2 4 5
4 3 3
1 3 2
3 4 3
3 2 5
10 10

样例输出 #1

15

提示

对于 $20%$ 的数据,$3\leq n,q\leq 16$。

对于 $40%$ 的数据,$3\leq n,q\leq 30$,$0\leq c_j,f_j\leq 50$。

对于 $60%$ 的数据,$3\leq n\leq 100$,$1\leq q\leq 5\times 10^4$,$0\leq cost_i,fr_i,c_j,f_j\leq 100$。

对于另外 $20%$ 的数据,对于每次买花,都有 $f_j=0$。

对于 $100%$ 的数据,$3\leq n\leq 500$,$\boldsymbol{1\leq q\leq 10^6}$,$0\leq cost_i,fr_i,c_j,f_j\leq 500$,$1\leq be_i \leq 10^6$。

题解

题目分析

这道题目是一个多重限制的01背包变种,而且一个限制是限制最大,另一个是限制最小

三维

状态表示方式:

dp[i][j][k],表示前i朵花,费用最大为j,新鲜度最少为k的状态中美丽度最大的状态

状态转移:

转移方式
不选第i枝花

直接由dp[i-1][j][k]转移来

选第i枝花(判断是否满足限制金额大于等于第i枝花的金额)

1.当前的花(第i枝花)直接能满足k需求(即第i枝花的新鲜度大于k)
2.第i枝花新鲜度不够k,从之前减去第i枝花金额的j和减去第i枝花新鲜度的k的状态转移过来

dp[i][j][k]=dp[i-1][j][k];
if(j>=cost[i])
{
	if(k<=fr[i])dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-cost[i]][0]+be[i]);
	{
		dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-cost[i]][0]+be[i]);
	}
	else if(dp[i-1][j-cost[i]][k-fr[i]]!=0)
	{
		dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-cost[i]][k-fr[i]]+be[i]);
	}
}
状态转移的解释(选的情况,不选的不用说了吧)

1.如果满足第一种情况的条件,则证明第i枝花的新鲜度大于k,可以直接从什么都不选的状态(即dp[i-1][j][0])转移到只选这一枝花的状态,然后再与当前的状态(不选这枝花)进行比较,选出较大的,从而更新该状态
2.如果满足第二种情况的条件,则证明不满足第一种状态,即第i枝花新鲜度没有k大(咱用的else if要是满足了就不会执行这种情况代码了),但是要想满足选第i枝花的情况,所以只能想办法找到之前满足不选第i枝花,金额限制为当前的j减去第i枝花的金额,新鲜度限制为当前的k减去第i枝花的新鲜度,即dp[i-1][j-cost[i]][k-fr[i]]的状态再加上第i枝花的美丽度,就是多种花加起来的状态满足限制

关于状态转移的疑问
1.选第i枝花的情况为什么还要分两种情况考虑

如果单纯用第二种情况的转移方程会出现k-fr[i]<0的情况,超出数组范围,所以做判断

2为什么选择的情况的第二种情况要判断dp[i-1][j-cost[i]][k-fr[i]]是否大于0

假如说dp[i-1][j-cost[i]][k-fr[i]]的状态等于零,说明不存在这样的情况,所以不能用了

注意事项

每次dp完之后要将数组初始化,否则很可能出问题

40pts代码

#include<iostream>
#include<cstring>
using namespace std;
const int N=510;
int dp[N][N][N];
int cost[N],fr[N],be[N];
int n,q;
int main()
{
    memset(dp,0,sizeof dp); 
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&cost[i],&fr[i],&be[i]);
    while(q--)
    {
        int c,f;
        scanf("%d%d",&c,&f);
        for(int i=1;i<=n;i++)
            for(int j=0;j<=c;j++)
                for(int k=0;k<=f;k++)
                {
                    dp[i][j][k]=dp[i-1][j][k];
                    if(j>=cost[i])
                    {
                        if(k<=fr[i])dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-cost[i]][0]+be[i]);
                        else if(dp[i-1][j-cost[i]][k-fr[i]]!=0)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-cost[i]][k-fr[i]]+be[i]);
                    }
                }
        printf("%d\n",dp[n][c][f]);
    }
    return 0;

分析无误,但时间复杂度过于吓人!(举例爆空间也不远了)
image
image

优化!优化!

二维

优化方式

将第一维枚举每枝花的操作用滚动数组代替

状态表示

dp[j][k]表示费用最大为j,新鲜度最少为k的状态中美丽度最大的状态

状态转移

转移方式
不选第i枝花

dp[j][k]的历史值(i-1情况下)

选第i枝花

同三维

if(k<=fr[i])
{
    dp[j][k]=max(dp[j][k],dp[j-cost[i]][0]+be[i]);
}
else if(dp[j-cost[i]][k-fr[i]]!=0)
{
    dp[j][k]=max(dp[j][k],dp[j-cost[i]][k-fr[i]]+be[i]);
}

注意事项

1.要将j反向枚举,因为状态转移方程中的dp[j-cost[i]][0]+be[i]和dp[j-cost[i]][k-fr[i]]+be[i]都会用到前一枝花的参数,即dp[j-cost[i]][0]+be[i]和dp[j-cost[i]][k-fr[i]]+be[i]的历史值(i-1情况下),如果从小到大枚举会导致其提前更新
2.要将j的最小值设置成cost[i]防止出现负下标
为什么不用枚举j<cost[i]的状态了呢?因为j<cost[i]的状态为不选第i枝花,而f[j][k]的历史值就是i-1情况不选的状态

40pts代码(为什么又是。。。)

#include<iostream>
#include<cstring>
using namespace std;
const int N=510;
int dp[N][N];
int cost[N],fr[N],be[N];
int n,q;
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&cost[i],&fr[i],&be[i]);
    while(q--)
    {
        memset(dp,0,sizeof dp);
        int c,f;
        scanf("%d%d",&c,&f);
        for(int i=1;i<=n;i++)
            for(int j=c;j>=cost[i];j--)
                for(int k=f;k>=0;k--)
                    if(k<=fr[i])dp[j][k]=max(dp[j][k],dp[j-cost[i]][0]+be[i]);
                    else if(dp[j-cost[i]][k-fr[i]]!=0)dp[j][k]=max(dp[j][k],dp[j-cost[i]][k-fr[i]]+be[i]);	
        printf("%d\n",dp[c][f]);
    }
    return 0;
}

but,我们的空间复杂度优化了真的不少!!!
image
image

继续优化!!!

多次询问的集中处理

我们注意到题目中cost[],fr[],be[]还有我们的dp[][]数据规模只有500,那么即使我们在一开始就根据数据规模和题目提供的每枝花的参数把所有的的情况都跑一遍,计算量也不会很大
而且我们之前对于每一次询问都会跑一遍,进行了很多不必要的重复计算,因此我们可以根据开始跑出来的结果,输入对应的金额限制和新鲜度总和限制查询dp数组中的数据即可(当然,我们的初始化操作也省了)

三维dp优化后的80pts

#include<iostream>
#include<cstring>
using namespace std;
const int N=510;
int dp[N][N][N];
int cost[N],fr[N],be[N];
int n,q;
int main()
{
    memset(dp,0,sizeof dp); 
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&cost[i],&fr[i],&be[i]);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=500;j++)
        for(int k=0;k<=500;k++)
        {
            dp[i][j][k]=dp[i-1][j][k];
            if(j>=cost[i])
            {
                if(k<=fr[i])dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-cost[i]][0]+be[i]);
                    else if(dp[i-1][j-cost[i]][k-fr[i]]!=0)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-cost[i]][k-fr[i]]+be[i]);
                }
            }
    while(q--)
    {
        int c,f;
        scanf("%d%d",&c,&f);
        printf("%d\n",dp[n][c][f]);
    }
    return 0;
}

image
image

时间复杂度好多了!空间嘛。。。。。。。。。

二维dp,AC!!!!!!

#include<iostream>
#include<cstring>
using namespace std;
const int N=510;
int dp[N][N];
int cost[N],fr[N],be[N];
int n,q;
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&cost[i],&fr[i],&be[i]);
    for(int i=1;i<=n;i++)
        for(int j=500;j>=cost[i];j--)
            for(int k=500;k>=0;k--)
                if(k<=fr[i])dp[j][k]=max(dp[j][k],dp[j-cost[i]][0]+be[i]);
                else if(dp[j-cost[i]][k-fr[i]]!=0)dp[j][k]=max(dp[j][k],dp[j-cost[i]][k-fr[i]]+be[i]);
            
    while(q--)
    {
        int c,f;
        scanf("%d%d",&c,&f);
        printf("%d\n",dp[c][f]);
    }
    
    return 0;
}

image
image

时空都比较可观!!!

加上读入优化?

#include<iostream>
#include<cstring>
using namespace std;
const int N=510;
int dp[N][N];
int cost[N],fr[N],be[N];
int n,q;
template<class T>void read(T &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9')  {f|=(ch=='-');ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return;
}
int main()
{
    read(n),read(q);
    for(int i=1;i<=n;i++)read(cost[i]),read(fr[i]),read(be[i]);
    for(int i=1;i<=n;i++)
        for(int j=500;j>=cost[i];j--)
            for(int k=500;k>=0;k--)
                if(k<=fr[i])dp[j][k]=max(dp[j][k],dp[j-cost[i]][0]+be[i]);
                else if(dp[j-cost[i]][k-fr[i]]!=0)dp[j][k]=max(dp[j][k],dp[j-cost[i]][k-fr[i]]+be[i]);  
    
    while(q--)
    {
        int c,f;
            read(c),read(f);
            printf("%d\n",dp[c][f]);
    }
    
    return 0;
}

image

好像再快不了了。。

最后有一个问题:转化成二维之后为啥k也要反向?

for(int i=1;i<=n;i++)
        for(int j=500;j>=cost[i];j--)
            for(int k=500;k>=0;k--)
                if(k<=fr[i])dp[j][k]=max(dp[j][k],dp[j-cost[i]][0]+be[i]);
                else if(dp[j-cost[i]][k-fr[i]]!=0)dp[j][k]=max(dp[j][k],dp[j-cost[i]][k-fr[i]]+be[i]);
如果我们不将k反向,会出现如下的错误


这个问题着实难道我了,思索良久也毫无头绪。
知道我打开了这道题的讨论,发现了一个标题:注意零元购
我忽然就明白了:当cost[i]=0时,dp[j-cost[i]][k-fr[i]]+w[i]就等于dp[j][k-fr[i]]+w[i],而如果从小到大枚举k的话dp[j][j-fr[i]]明显不是历史值(i-1状态),肯定被更新过了

结尾

编者旨在用自己的心路历程帮到广大OIer更深刻理解01背包问题,同时在编写过程中加深自己的理解和表达
如有大佬有更妙的解法,请留下高见

标签:fr,01,P8548,int,买花,leq,cost,枝花,dp
From: https://www.cnblogs.com/qlhoier/p/17047826.html

相关文章

  • Unix环境高级编程-01:环境配置和第一个ls程序
    环境配置和第一个ls程序一、环境配置下载apue3的代码(apue表示Unix环境高级编程的英文简写,3表示第三版)下载地址:http://www.apuebook.com/src.3e.tar.gz,书籍地址:http://w......
  • 2014蓝桥
    中国古代文献中,曾记载过“大衍数列”,主要用于解释中国传统文化中的太极衍生原理。它的前几项是:0、2、4、8、12、18、24、32、40、50...其规律是:对偶数项,是序号平方再......
  • 剑指offer代码 vs2019执行
    方法:代码文件夹名称为:CodingInterviewChinese2-master1.用vs2019加载解决方案.sln文件  2.一个解决方案下面有多个项目,通过右键解决方案->属性->通用属性->启动......
  • Hadoop学习笔记01
    一、大数据概念大数据​大数据(BigData):指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合。主要解决问题海量数据的采集存储和分析......
  • 树上分块解决限制距离的树上 DP 问题([NOI2014] 购票)
    [NOI2014]购票大家好,我喜欢暴力数据结构,所以我用分块过了此题。转移方程很简单:\[f_u=\min_{d_u-d_v\leql_u}{(d_u-d_v)\timesp_u+q_u+f_v}\]\[f_u=d_u\timesp_u+q......
  • 0112总结
    四道题都比较套路,AK了。T1[模拟赛20230112]密接枚举区间的左端点,再枚举众数出现的次数,那么满足条件的右端点就是一段区间。令\(pos1_i\)为第一个出现\(i\)次的数的......
  • 【题解】P4899 [IOI2018] werewolf 狼人
    そうやってただ日が暮れるまで語り掛ける本当の言葉题意给定一个有向图和若干询问,每次询问是否存在一条满足条件的路径:端点分别为\(u,v\)前面一段不经过\([1,L......
  • 2019, Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Locali
    AbstractGradient-weightedClassActivationMapping,usesthegradientsofanytargetconceptflowingintothefinalconvolutionallayertoprodeceacoarselo......
  • S2-037 CVE-2016-4438 远程代码执行
    漏洞名称S2-037CVE-2016-4438远程代码执行利用条件Struts2.3.20-StrutsStruts2.3.28.1使用了REST插件漏洞原理ApacheStruts2在使用REST插件的情况下,攻击者使......
  • Nginx基础01:安装和基本使用
    背景Nginx是一个高性能的Web服务器,几乎所有的Web服务都需要使用Nginx。关于Nginx的功能特性这里不再赘述,让我们从0开始,了解Nginx的基本用法,学习它在Web服务中都有哪些应......