首页 > 其他分享 >P1802-DP【橙】

P1802-DP【橙】

时间:2023-11-02 12:44:48浏览次数:36  
标签:const 常量 int remain cdP P1802 DP

1.又是一道因为写了异常剪枝而调了好久的题,以后再也不写异常剪枝了,异常情况压根不该出现,所以针对出现的异常情况进行补救的异常剪枝是一种很容易出错的行为,做为两手准备也就罢了,但第一次写成的代码必须能在没有异常剪枝的情况下算出正确结果才行!

2.还提出了一个专门针对记搜的编码规范:编写记忆化搜索的时候不要使用除了DP以外的全局变量,要用外界常量就用一个一直传着的常量引用如const int &
(注意,指向常量的指针写作int * const p,而常量引用写作 const int & p,但两者是同一个东西,都是不允许修改指向对象的,注意,指向常量的指针和常量引用都并不是只能指向常量,而是不能修改指向的量,换句话说可以指向变量,只是用指针和引用来表示指向的变量的时候那个变量会表现成一个常量的样子,但并不是新创建了一个与之相等的常量来被指)

3.同时,十年OI一场空,不开ll见祖宗啊QAQ
而且很多时候把int改成ll会忘了改返回值类型等较小的地方,导致错误,所以不如#define int long long,signed main,真香

4.然后还是WA了,因为忽略了还有重量为0的商品,即不用嗑药也能打过的菜鸡,所以边界应该是“if(remain<0||cdP==0)return DP[remain][cdP]=0;//边界剪枝”而不是“if(remain==0||cdP==0)return DP[remain][cdP]=0;//边界剪枝”

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
#define int long long
int DP[1005][1005];
//remian is the remain count of drug ,and cdP is the considered_person_number
//the return value is the answer of I have these drugs and these persons
//标准编码规范:编写记忆化搜索的时候不要使用除了DP以外的全局变量,要用外界常量就用一个一直传着的常量引用如const int & 
int dfs(int remain,int cdP, const int * const w,const int * const u)
{
	if(DP[remain][cdP]!=-1)return DP[remain][cdP];//记忆化剪枝
	if(remain<0||cdP==0)return DP[remain][cdP]=0;//边界剪枝
	int DFS=0;//总种数就加、最优解就取MAX(或MIN)
	if(remain-u[cdP]>=0)DFS=max(DFS,dfs(remain-u[cdP],cdP-1,w,u)+w[cdP]);
	DFS=max(DFS,dfs(remain,cdP-1,w,u));
	return DP[remain][cdP]=DFS;
}
 
signed main()
{
	int x,n,ans=0,l[1005],w[1005],u[1005];
	cin>>n>>x;
	memset(DP,-1,sizeof(DP));
	for(int i=1;i<=n;i++)
		cin>>l[i]>>w[i]>>u[i];
	for(int i=1;i<=n;i++)w[i]-=l[i],ans+=l[i];
	cout<<5*(ans+dfs(x,n,w,u))<<endl;
	
    return 0;
}

标签:const,常量,int,remain,cdP,P1802,DP
From: https://www.cnblogs.com/gongkai/p/17805141.html

相关文章

  • P1164-DP【橙】
    这道题让我更深入的理解了记忆化搜索的过程,既然记忆化搜索的结果要靠返回值来传递,那么记忆化搜索解决问题的必须是倒序的,即记忆化搜索是一个简化问题倒序解决的过程,普通搜索是一个复杂化问题逐步尝试并记录尝试结果的过程。特别是对于求总种数的记忆化搜索,就是把能干的事情组合起......
  • matplotlib 设置图形大小 figsize dpi
    figure语法说明figure(num=None,figsize=None,dpi=None,facecolor=None,edgecolor=None,frameon=True)num:图像编号或名称,数字为编号,字符串为名称figsize:指定figure的宽和高,单位为英寸dpi:指定绘图对象的分辨率,即每英寸多少个像素,缺省值为80,1英寸等于2.5cm,A4纸是21......
  • Qt通过UDP发送广播
      //x.hQUdpSocket*udp=nullptr;//UDP对象voidcreateUdpAndSendData();//创建UDP对象和发送广播数据voiddropUdp();//释放UDP对象voidreadData();//用来接收其他设备发送的数据voidcreateUdpAndSendData(){......
  • P1216-DP【橙】
    在这道题中,我第一次用了memset,确实方便,不过需要注意的是只有全部赋值-1和0的时候才能使用它,否则他能干出吓死人的事。以及memset在cstring头文件里,在本地就算不include也能照常编译,但评测机里可能不行,所以一定要写上cstring同时,我半获得半自我总结了一个暴论,这个暴论直接让我理解......
  • 验证2个节点udp和tcp可通性
    -u表示udp,默认是tcp。-l表示作为server监听。server:192.168.0.104上开启udp123端口server发送11client:连接192.168.0.104上udp123端口client发送100 server:192.168.0.104上开启tcp123端口server发送102client:连接192.168.0.104上tcp123端口client发送101......
  • ThreadPoolExecutor使用浅谈
    1.基础介绍ThreadPoolExecutor是Python标准库concurrent.futures模块中的一个类,用于实现线程池的功能。ThreadPoolExecutor模块相比于threading等模块,通过submit方法返回的是一个Future对象,它代表了一个未来可期的结果。通过Future对象,我们可以在主线程(或主进程)中获取某个线程(......
  • DP查缺补漏之多重背包优化原理
    DP查缺补漏之多重背包优化原理普通思路类似完全背包for(inti=1;i<=n;i++)for(intj=1;j<=V;j++)for(intk=1;k<=V/c[i];k++){if(k*c[i]<=j)f[i][j]=max(f[i-1][j],f[i-1][j-k*c[i]]+k*w[i]);......
  • poj 2411 状压dp入门题
    Mondriaan'sDreamTimeLimit:3000MS MemoryLimit:65536KTotalSubmissions:29096 Accepted:15505DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,afterproducingthedrawingsinhis�......
  • UDP 协议
    UDP协议UDP(UserDatagramProtocol),目标是在传输层提供直接发送报文(Datagram)的能力。Datagram是数据传输的最小单位。UDP协议不会帮助拆分数据,它的目标只有一个,就是发送报文。   与tcp差异  ......
  • CF练习题17(DP)
    ChocolateBar我们看到\(n,m\le30\)想到暴搜。考虑枚举分割线,一直到刚好满足需要或者只有一个巧克力的情况。随手跑了个最优解。inlineintdfs(intn,intm,intk){ if(n*m==k)return0; if(k<=0)return0; if(f[n][m][k]<inf)returnf[n][m][k]; intres=inf; up(i,......