5月 DP 做题记录

前言

见一位同学，发出每天切一道dp挑战，见后有感，我也来？？？

但我不会每天都写一篇哈哈。

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

目录

  • P8329 [ZJOI2022] 树
  • P6734 [Wdsr-2] 阴阳玉
  • P8321 [JROI-4] 沈阳大街 2
  • P3195 [HNOI2008] 玩具装箱
  • P1450 [HAOI2008] 硬币购物
  • P1654 OSU
  • CF453A Little Pony and Expected Maximum
  • P7395 弹珠游戏
  • P1896 [SCOI2005] 互不侵犯
  • P1539 [TJOI2011] 01矩阵
  • P1552 [APIO2012] 派遣
  • P2110 欢总喊楼记
  • P1281 书的复制
  • AT5801 [AGC043D] Merge Triplets
  • P3698 [CQOI2017] 小Q的棋盘
  • P3239 [HNOI2015] 亚瑟王
  • P2365 任务安排
  • P3572 [POI2014] PTA-Little Bird
  • P4832 珈百璃堕落的开始
  • P1439 【模板】最长公共子序列
  • P8356 「WHOI-1」数列计数
  • P3296 [SDOI2013] 刺客信条
  • P4072 [SDOI2016] 征途
  • P8352 [SDOI/SXOI2022] 小 N 的独立集

//--------------------------------------------------------------------------------------------------------------------------

P8329 [ZJOI2022] 树

二维计数动态规划，本来想等周日写一篇题解的，但发现周六就已经过了六篇了，估计轮不到我了。

AC Record

核心转移方程：

f[j+1][k+1]=dp(f[j+1][k+1],a);
f[j+1][k]=f[j+1][k]+...;
f[j][k+1]=dp(f[j][k+1],a);

//--------------------------------------------------------------------------------------------------------------------------

P6734 「Wdsr-2」阴阳玉

这道题非常好！一道将数学和 dp 完美融合在一起的题。但是，直接 dp 没有办法最优，会T掉，这个时候需要用到 dp 优化，矩阵加速优化。最后进行分类讨论。

AC Record

核心转移方程：

f[m][i][j]=dp(f[m][i][j],f[m-1][k][j]*f[m-1][i][n]);

//--------------------------------------------------------------------------------------------------------------------------

P8321『JROI-4』沈阳大街 2

看题面觉得是一个概率 dp，就觉得考的是数学期望；但实际就是一个普普通通的 dp（这个傻子第一个思路就硬往期望上想，后来写全排列的时候发现这就是个普通 dp...）

话说为什么我代码运行内存高达 $379 $MB，我看楼下几个就 \(700\) 多KB？？？

AC Record

核心转移方程：

f[i][j]=(f[i][j]+f[i-1][j-1]*b1*v);
f[i][j]=(f[i][j]+f[i-1][j-1]*b2*v);

//--------------------------------------------------------------------------------------------------------------------------

P3195 [HNOI2008] 玩具装箱

一道斜率优化 dp，只不过一个斜率优化好像不太够，需要加一个二分，但是硬生生没看出来和单调队列有什么关系啊。。。。

AC Record

核心转移方程：

s[i]+=s[i-1],a[i]=s[i]+i,b[i]=a[i]+len+1;

之后斜率优化就是算一下斜率判定一下就好。

//--------------------------------------------------------------------------------------------------------------------------

P1450 [HAOI2008] 硬币购物

先求出无限制的方案数，再减去单个硬币超限的情况，然后加上两个硬币超限的情况，再减去硬币超限的情况，最后再加上四个硬币超限的情况，即为最终答案。容斥原理！！！

AC Record

核心转移方程

f[j]=f[j]+f[j-a[i]];

//--------------------------------------------------------------------------------------------------------------------------

P1654 OSU

每次代价都增加 \(1\)，也就是平方和立方的增量是 \(1\)，利用开始的两个公式和维护的值就可以递推。

AC Record

核心转移方程

b[i]=(b[i-1]+1)*a[i]
.........
(三个基本一样的式子)

//--------------------------------------------------------------------------------------------------------------------------

CF453A Little Pony and Expected Maximum

数学概率与期望。（但好像可以直接猜结论）

AC Recod

核心转移方程

i+=dp(j/m,n)-dp(j-1)/m,n)*j;

//--------------------------------------------------------------------------------------------------------------------------

P7395 弹珠游戏

打个表出来，表示所有能走的情况，然后 DP ，比较恶心的是这个还得加上博弈论和记忆化......

AC Record

核心转移方程

dp[5][i*4+j]=bi*4+bj;
dp[5][i*4+j]=ai*4+aj;

//--------------------------------------------------------------------------------------------------------------------------

P1896 [SCOI2005] 互不侵犯

状压的核心就是把一行、一列数用二进制数来表示。那么对于这道题，每一行的状态（即1为放0为不放）由上一行和自身是否符合条件决定。那么状态是可以先预处理出来的。

另外在预处理还有一个小技巧，就是判断国王是否相邻，即i&(i<<1)，为0就是合法的，这在状态转移时判断上下两行的放置是否合法也是能用的。

AC Record

核心转移方程

f[i][j][q]+=f[i-1][k][q-a[j]];

//--------------------------------------------------------------------------------------------------------------------------

P1539 [TJOI2011] 01矩阵

想到矩阵在不同情况下最短边 \(MAX\) 为 \(15\)，正好可以状压\(dp\)。

AC Record

核心转移方程

f[i][j]=(f[i][j]+f[i-1][k])%p;

//--------------------------------------------------------------------------------------------------------------------------

P1552 [APIO2012] 派遣

核心想法：钱越少人越多最棒。

AC Record

核心转移方程

f[i]=dp(f[i],a[j]*b[j]);

//--------------------------------------------------------------------------------------------------------------------------

P2110 欢总喊楼记

在 dfs 参数中带入最高位的数字，所有数位枚举，判断最低是否等于最高。

这题还要考虑前导零，不过不需要像其他的数位 dp 那样在 dfs 参数中带 bool 变量记录或者 dp 数组里多开一维，因为我们有最高位的数字，当最高位不是 0 时就说明没有前导零。

当出现第一个非 0 位，就得到了最高位的数。

AC Record

核心转移方程

k=k*10+a[i];

//--------------------------------------------------------------------------------------------------------------------------

P1281 书的复制

一道二分题

然后我懒得想了

直接dp+dfs+前缀和

AC Record

核心转移方程

dp[i][j]=min(dp[i][j],max(dp[i-1][k],a[j]-a[k]));

//--------------------------------------------------------------------------------------------------------------------------

AT5801 [AGC043D] Merge Triplets

考虑对于要计数的排列 \(p\)（长度为 \(3n\)）进行划分，化成长度为 \(3\) 的 \(n\) 组。我们考虑过 \(p_1\) 的那个组需要满足什么条件。

考虑 \(i\) 的下方是 \(j\) 需要满足什么条件。

直接 dp 维护差值。

AC Record

核心转移方程

dp(f[i+1][j+1],f[i][j]);
dp(f[i+2][j-1],cnt1);	
dp(f[i+3][j],cnt2);
dp(ans,f[n][i]);

//--------------------------------------------------------------------------------------------------------------------------

P3698 [CQOI2017]小Q的棋盘

往下走回来，走 \(a\) 步，结点够，一定能够访问到 \(\frac {k} {2}\)个结点。对于一个结点，我们枚举一个它的子结点和一个在子结点中走的步数，得到可以不返回时的访问数再加上走剩下的子树且一定返回的访问数。

AC Record

核心转移方程

dp(n,a+(m-a+1)/2)

//--------------------------------------------------------------------------------------------------------------------------

P3239 [HNOI2015]亚瑟王

用每张牌的发动概率 \(g[i]\) 乘那张牌的伤害 \(d[i]\)，最后根据期望的线性性质相加即可。

AC Record

核心转移方程

f[i][j]=f[i-1][j]*dp[k-j];
a=f[i-1][j-1]*(1-dp[k-j+1]);
f[i][j]+=a;

//--------------------------------------------------------------------------------------------------------------------------

P2365 任务安排

斜率优化动态规划

AC Record

核心转移方程

dp[i]=min(dp[i],dp[j]+f*(b[n]-b[i-1]));

//--------------------------------------------------------------------------------------------------------------------------

P3572 [POI2014]PTA-Little Bird

单调队列+DP。

保证单调队列里的元素相同体力消耗下靠近队首的高度尽量高即可，

相当于在维护队列体力消耗值从队首到队尾递增的基础上对高度进行递减的维护。

AC Record

核心转移方程

f[i]=f[d[l]]+(a[d[l]]<=a[i]);

//--------------------------------------------------------------------------------------------------------------------------

P4832 珈百璃堕落的开始

问题转为背包问题：每个式子抽象成物品，\(s?c\)抽象成重量，而我们的目标是找到总重量为0时的最大价值，价值抽象成s（或者c），因为每一对配对的s和c价值为1。

AC Record

核心转移方程

ans=max(ans,r[i]+l[i]+i);

//--------------------------------------------------------------------------------------------------------------------------

P1439 【模板】最长公共子序列

板子题，方法较多，dp + 二分 挺舒服的

AC Record

核心转移方程

dp[lower_bound(f,dp[x])-f]=dp[x];

//--------------------------------------------------------------------------------------------------------------------------

P8356 「WHOI-1」数列计数

优化递归（爆搜）的 ---->> 递归转递推

AC Record

核心转移方程

f[k][j]=(f[!k][j-1]+f[!k][j])%M;
f[k][j]=f[!k][j];

//--------------------------------------------------------------------------------------------------------------------------

P3296 [SDOI2013]刺客信条

md 散兵阳间题目

我该开始拿数据结构肝了半天，写了近三百行的代码，把手都给我写废了，之后还卡了两波 MLE。后来AC之后才知道可以dp挖艹。

AC Record

核心转移方程

ans = min(ans,f[i]+dp[j]-w[i][j])

//--------------------------------------------------------------------------------------------------------------------------

P4072 [SDOI2016]征途

考虑斜率优化

假设 \(j\) 比 \(k\) 更优，则有 \(dp[j]+(sum[i]-sum[j])^2

然后展开移项即可

AC Record

核心转移方程

m*f[m][n]-dp[n]*dp[n]

//--------------------------------------------------------------------------------------------------------------------------

P8352 [SDOI/SXOI2022] 小 N 的独立集

状态合并存到树里，然后 dp 套 dp ，最后 dfs；

AC Record

核心转移方程

dp[j][a]=f[l][j][a];
f[l][j][a]=0;

//--------------------------------------------------------------------------------------------------------------------------

2022年随笔

相关

标签