首页 > 其他分享 >P1004 [NOIP2000 提高组] 方格取数 题解

P1004 [NOIP2000 提高组] 方格取数 题解

时间:2023-12-03 20:58:18浏览次数:40  
标签:NOIP2000 题解 P1004 路径 两条 dp

题意:

思路:

考虑四维 $ dp $ :

设 $ dp[i][j][k][l] $ 表示两条路径分别走到 $ (i,j) $ 和 $ (k,l) $ 时所能获取的最大和,显然会超时。

考虑三维 $ dp $ :

设 $ dp[i][j][k] $ 表示两条路径走了 $ i $ 步分别走到第 $ j $ 行和第 $ k $ 行时所能获取的最大和,通过当前步数 $ i $ 以及当前行数 $ j $ 和 $ k $ ,可以得出两条路径分别走到第 $ i + 2 - j $ 列和第 $ i + 2 - k $ 列,那么状态转移方程有:

$ dp[i][j][k] = max(dp[i - 1][j][k],dp[i - 1][j - 1][k],dp[i - 1][j][k - 1],dp[i - 1][j - 1][k - 1]) + a[j][i + 2 - j] + a[k][i + 2 - k] $

当且仅当 $ j = k $ 时,两条路径走到同一点,由于不能重复取值,那么状态转移方程有:

$ dp[i][j][k] = dp[i][j][k] - a[j][i + 2 - j] $ $ dp[i][j][k] = dp[i][j][k] - a[k][i + 2 - k] $

标签:NOIP2000,题解,P1004,路径,两条,dp
From: https://www.cnblogs.com/ShawyYum/p/17873731.html

相关文章

  • vue 编辑器+使用场景+问题解决
    vue编辑器组件添加依赖"dependencies":{"@codemirror/autocomplete":"^6.4.2","@codemirror/commands":"^6.2.1","@codemirror/lang-javascript":"^6.0.2","@codemirror/lan......
  • SP1716 GSS3 - Can you answer these queries III 题解
    题意:给定一个长度为$n$的序列$a$,$q$次操作,每次操作为以下之一:\(0\)\(x\)\(y\):将\(a_x\)修改为\(y\)\(1\)\(l\)\(r\):询问区间\([l,r]\)的最大连续子序列和思路:考虑线段树维护区间最大连续子序列和:线段树每个节点需要维护的信息:区间左端点$l$,区......
  • P3214 [HNOI2011] 卡农 题解
    Description给定\(n,m\),要从\(1,2,\dots,2^n-1\)中选\(m\)个无序的数,使得他们互不相同且异或和为\(0\),问有多少种选法。对\(998244353\)取模。Solution考虑求出有序的方案数的个数再除以\(m!\)。设\(f_i\)表示选出\(i\)个数的方案。那么如果随便选前\(i-1\)......
  • ABC331G题解
    ABC331G日常被bot吊打罢了。首先注意到一件事是你需要求一堆max的期望对吧。所以其实上来就应该试试上min-max容斥的。但是鉴于我没有脑子,所以其实没想到也可以理解。先来复习一下式子:\[Emax(S)=\sum_{T\subsetS}Emin(T)(-1)^{\midT\mid-1}\]所以带入要求的东西......
  • ICPC2022Hangzhou C No Bug No Game 题解
    LinkICPC2022HangzhouCNoBugNoGameQuestion给定\(n\)个物品和上限\(k\),要求最大化分数,物品的选择顺序可以任意第\(i\)个物品一行\(p_i\)代表个数,后面\(p_i\)个\(w_j\)代表容量,定义\(sum=\sum\limits_{j=1}^{i-1}\),对于第\(i\)个物品\(sum+p_i\lek\)......
  • ICPC2022Hangzhou A Modulo Ruins the Legend 题解
    LinkICPC2022HangzhouAModuloRuinstheLegendQuestion求$$\sum\limits_{i=1}^na_i+n\timess+\frac{n(n+1)}{2}\timesd\modm$$的最小值Solution我们把这个式子看成一一个二元不定方程\(ax+by+sum\modm\)的最小值,其中\(a=n,b=\frac{n(n+1)}{2},sum=\sum\limits......
  • ucup nanjing 题解
    比赛链接D收获很大的一道题首先考虑朴素的\(dp\),令\(f_{x,i}\)为\(x\)子树中的每一个叶子到\(x\)的距离都为\(i\)的最小代价不难列出\(dp\)式子为:\(f_{x,i}=\min\limits_{i\in\{0,1\}}\{cost(u,i)+\sum\limits_{v\inson(u)}f_{v,x-i}\}\),其中\(cost(u,i)\)为把......
  • CF1288题解
    CF1288EducationalCodeforcesRound80(RatedforDiv.2)A略CF1288BlinkCF1288B题意给定\(A,B\),问有多少个二元组\((a,b)\)满足\(1\lea\leA,1\leb\leB\)且\(a\cdotb+a+b=\operatorname{conc}(a,b)\)。其中\(\operatorname{conc}(a,b)\)表示将\(a,b\)......
  • [ABC017D] サプリメント 题解
    题目传送门~一道DP前缀和优化好题。题目分析首先,朴素DP非常好想。可以从后向前考虑,设\(f_i\)表示从第\(i\)个补品开始的摄取方法数。摄取一个补品:\(f_i=f_{i+1}\)摄取两个补品:\(f_i=f_{i+2}\)以此类推。则转移方程为:\[f_i=f_{i+1}+f_{i+2}+\dots+f_{j......
  • P4143 采集矿石 题解
    题目传送门给出字符串\(s\),以及数组\(a_1\sima_{|s|}\)。定义一个子串的排名为:字典序比它大的本质不同的子串个数\(+1\)。定义一个子串\(s[l,r]\)的权值为\(\sum\limits_{i=l}^ra_i\)。求有多少个子串的排名等于权值。\(|s|\le10^5,0\lea_i\le1000\)。......