首页 > 其他分享 >20240130-DP以及优化随记

20240130-DP以及优化随记

时间:2024-02-03 09:45:37浏览次数:27  
标签:背包 int max --- DP 20240130 dp 随记

状态转移方程

  • 递归关系 (从已知求得未知的表达式)

背包dp

  • 0-1 背包,多重,完全,混合

  • 模版套用

//多重背包
#include<bits/stdc++.h>
using namespace std;
const int N=507,M=1e5+7;
int p,n,x,y,z,dp[10005]; 
int main(){
	cin>>p>>n;
	for(int i=1;i<=n;i++){
		scanf("%d %d %d",&x,&y,&z);
		int t=1;
		while(t<=x){
			for(int j=p;j>=y*t;j--)dp[j]=max(dp[j],dp[j-y*t]+z*t);
			x-=t;
			t*=2;
		}
		if(x){
			for(int j=p;j>=y*x;j--)dp[j]=max(dp[j],dp[j-y*x]+z*x);
		}
	}
	printf("%d",dp[p]);
	return 0;
}

区间dp,线性dp

  • 令状态 f(i,j) 表示 ij 所有元素合并能获得的价值的最大值

  • f(i,j)=max(f(i,k)+f(k+1,j)+cost)

树形dp

  • 在树上进行dp

  • 待办:树

单调队列优化

  • 比你小还比你强()

  • RMQ 操作(区间最大/小值)

注意数组大小

  • dp[505][505] ---> RE

  • dp[5005][5005] ---> MLE

标签:背包,int,max,---,DP,20240130,dp,随记
From: https://www.cnblogs.com/Firepaw-cattery/p/18004360

相关文章

  • 20240201-高级数据结构随记
    intmain(){intn;cin>>n;for(inti=1;i<=n;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];}intmn=sum[0];for(inti=1;i<=n;i++){//枚举右端点if(sum[i]-mn>ans)ans=sum[i]-mn;......
  • 20240202-训练赛随记
    机场检录//二分#include<bits/stdc++.h>usingnamespacestd;longlongn,m,a[100005];boolcheck(longlongx){longlongt=0;for(inti=1;i<=n;i++)t+=(x/a[i]);returnt>=m;}intmain(){cin>>n>>m;for(inti=1;i<......
  • 运输层的TCP与UDP协议(学习笔记)
    一、运输层1.逻辑通信结构2.端口号、复用与分用二、TCP与UDP的区别1.概览图2.用户数据报协议UDP(UserDatagramProtocol)UDP面向应用层报文,可以在任何时候发起传输(无连接),向上层提供不可靠传输服务,即如果传输过程中出现误码,也不会触发重传。可以支持一对一、......
  • 如何优雅的处理特殊的子集 dp 问题
    sosdp&高维前缀和求\[g_i=\sum_{j\&i>0}f_j(i\leq2^n-1)\]我们将\(i,j\)进行二进制拆分,拆成\(n\)个维度。类似于:\[g_{a_1,a_2,a_3,a_4,a_5...a_n}=\sum_{a_k\leqb_k}f_{b_1,b_2,b_3,b_4,b_5...b_n}(a_i,b_i\subseteq\{0,1\}......
  • AT_dp 26 题
    AT_dp26题A.Frog1直接dp。设\(f_i\)表示调到石头\(i\)的最小费用,则有\[f_i=\min(f_{i-1}+\left|a_i-a_{i-1}\right|,f_{i-2}+\left|a_i-a_{i-2}\right|)\]B.Frog2上一题的升级版,同样设\(f_i\)表示调到石头\(i\)的最小费用,则有\[f_i=\min_{j=i-k}^{i-1}f_j+\lef......
  • WordPress 技巧:解决 3.6 版本的 "wpdb::escape is deprecated" 错误提示
    来源:http://www.shanhubei.com/archives/13621.html升级到WordPress3.6之后,发现在debuglog中有很多以下的错误信息:Notice:wpdb::escapeisdeprecatedsinceversion3.6!Usewpdb::prepare()oresc_sql()instead.这个错误信息的意思是WordPress3.6将$wpdp类......
  • 代数最值与函数随记
    代数式\(ax^2+bx+c\)的最值是(),()时有最大值,()有最小值。代数解\[ax^2+bx+c\]\[=a(x^2+\frac{b}{a}x)+c\]\[=a[(x^2+\frac{b}{a}x+(\frac{b}{2a})^2]+c-\frac{b^2}{4a^2}·a\]\[=a(x+\frac{b}{2a})^2+\frac{4ac-b^2}{4a}\]\(\therefore\)易得,当\(x=-\fr......
  • SpringBoot利用ThreadPoolTaskExecutor批量插入百万级数据实测!
    开发目的: 提高百万级数据插入效率。采取方案: 利用ThreadPoolTaskExecutor多线程批量插入。采用技术: springboot2.1.1+mybatisPlus3.0.6+swagger2.5.0+Lombok1.18.4+postgresql+ThreadPoolTaskExecutor等。application-dev.properties添加线程池配置信息#异步线程配置#配置核......
  • ajax与action,WordPress主题开发之wp_ajax_{$action}和wp_ajax_nopriv_{$action}的区
    wp_ajax_{$action}和wp_ajax_nopriv_{$action}是WordPress主题开发常用的函数,这两个函数经常用在ajax交互功能上。例如ajax表单登录,ajax提交表单等。本篇文章主要讲述了wp_ajax_{$action}和wp_ajax_nopriv_{$action}之间的区别。WordPress中AJAX请求方式在说wp_ajax_{$action}......
  • 20240130
    Kotlin编程知识总结总结自《Android第一行代码》变量varval可变变量不可变变量自动类型推导:vala=10显式声明类型:vala:Int=10函数关键词funfunmethodName(param1:Int,param2:Int):Int{ return0}语法糖funmethodName(param1:Int,param2:Int):......