首页 > 其他分享 >DP

DP

时间:2023-01-12 22:58:50浏览次数:53  
标签:10 int max maxt DP dp

DP是什么

就我而言,DP是需要做出最优选择的一种题目,而且是全局最优的选择

DP有个性质,是相关性,就后面做的决策可以在之前做的决策上进行

而且没有后效性

数组的下标代表状态,数组中数的值代表value


贴一个题

D - Snuke Panic (1D) (atcoder.jp)

这个题的状态转移方程是dp[x][t]=max(dp[x-1][t-1],dp[x][t-1],dp[x+1][t-1])+a[x]

key : fup(j,0,min(4ll,i)

这道题一个很关键的地方就是上面的key,如果j>i的话,那就是不可能走到的,由此获得的状态也是不可能的,会干扰后续的计算

const int N=2e5+10;
int n,m,k,x,y,z;
int f[N][10],s[N][10];
void solve(){
	//try it again.
	cin>>n;
	int maxt=0;
	up(1,n){
		cin>>x>>y>>z;
		s[x][y]=z;
		maxt=max(maxt,x);
	}
	f[0][0]=0;
	fup(i,1,maxt){
		fup(j,0,min(4ll,i)){
			if(j){
				f[i][j]=max(f[i-1][j],f[i-1][j-1]);
			}
			f[i][j]=max({f[i-1][j],f[i-1][j-1],f[i-1][j+1]});
			f[i][j]+=s[i][j];
		}
	}
	int ans=0;
	for(int i=0;i<=4ll;i++)
		ans=max(ans,f[maxt][i]);
	// debug(ans);
	cout<<ans;
}

标签:10,int,max,maxt,DP,dp
From: https://www.cnblogs.com/liangqianxing/p/17048173.html

相关文章

  • Trick 8:子集卷只因的 SOSDP 做法
    问题引入:对于两个数组\(a\),\(b\),长度为\(2^n\),从\(0\)开始标号。求\(c_i=\sum\limits_{p\&q=i}a_pb_q\)。关于这个问题的求解,我们可以使用SOSDP完成一系列......
  • 状压 DP
    概述状压DP是以状态含有某种意义上的状态压缩为特点的一类DP。所谓状态压缩,通常指的是将各个元素的状态从常规的vector等编码映射为一个\(id\)即抽象的状态。......
  • DP 套 DP
    概述DP套DP通过DP/DFS处理出某个复杂DP的状态集,构建出对应的DAG,从而将复杂DP的难度有效降低,有时还伴有降低时空复杂度的效果。其实我不是很认同这个名字。......
  • 树上分块解决限制距离的树上 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......
  • python udp 接收图片并保存在本地
     疑问1.发送图片是以什么格式2.字节数据怎么保存到本地3.怎么对传输不同设备发送的图片进行分类存储4.udp实现解答1.以字节a.先用cv......
  • Oracle impdp使用content=data_only会阻塞其他会话DML操作
     Oracleimpdp使用content=data_only会阻塞其他会话DML操作 上篇提到了insert/*+append*/into会对表持有LOCKED_MODE=6的TM锁,导致其他对该表的DML都会被阻塞。实......
  • [NOIP2015 提高组] 子串 【计数dp】
    题面https://www.luogu.com.cn/problem/P2679分析CCF数据真的水。不过还是要写下正解:令\(dp[i][j][t][0/1]\)表示\(a\)串前\(i\)个字符,\(b\)串前\(j\)个字符,匹配子串数......
  • 数位 DP
    2023.1.9省选模拟赛IA【题意】给定\(x,y\),求\[\sum\limits_{i\in[0,2^k-x)}\sum\limits_{j\in[y,2^k)}[i\&j=0]\times[(i+x)\&(j-y)=0]\]\(......
  • UDP
    UDPUDP是一种全双工通信协议。UDP协议首部中有一个16位的大长度.也就是说一个UDP能传输的报文长度是64K(包含UDP首部)。如果我们需要传输的数据超过64K,就需要在应用层......
  • JUC源码学习笔记5——1.5w字和你一起刨析线程池ThreadPoolExecutor源码,全网最细doge
    源码基于JDK8文章1.5w字,非常硬核系列文章目录和关于我一丶从多鱼外卖开始话说,王多鱼给好友胖子钱让其投资,希望亏得血本无归。胖子开了一个外卖店卖国宴,主打高端,外卖......