当前位置: 首页 > web >正文

(区间 dp)洛谷 P6879 JOI2020 Collecting Stamps 3 题解

题意

给定一个周长为 L L L 的圆,从一个点出发,有 N N N 个黑白熊雕像,编号为 1 1 1 N N N,第 i i i 个雕像在顺时针 X i X_i Xi 米处,如果你没有在 T i T_i Ti 秒内收集到这个黑白熊雕像,那么这个雕像就会发出“唔噗噗噗”的声音然后爆炸。

现在 JOI 君在这个点,他每秒可以移动 1 1 1 米,顺时针或者逆时针的移动都是允许的。

JOI 君想问,他最多能收集到多少个黑白熊雕像?

1 ≤ N ≤ 200 1 \le N \le 200 1N200 2 ≤ L ≤ 1 0 9 2 \le L \le 10^9 2L109 1 ≤ X i < L 1 \le X_i<L 1Xi<L X i < X i + 1 X_i < X_{i+1} Xi<Xi+1 0 ≤ T i ≤ 1 0 9 0 \le T_i \le 10^9 0Ti109

思路

首当其冲破环成链。

发现可以顺时针或逆时针走,即可以停在区间的左或者右去收集雕塑。在洛谷 P1220 关路灯中同样是这样的套路,所以考虑朴素地设 f i , j , o p f_{i,j,op} fi,j,op 表示收集区间在 [ i , j ] [i,j] [i,j] 的雕塑,收集完之后要停在左或右端点,可以收集到最大雕塑数量。

但是这一题还有一个时间限制,要在特定的时间点之前(包括这个时间点)收集到特定的雕塑,不一定能将区间 [ i , j ] [i,j] [i,j] 的雕塑全部收集完。因此我们改变一下状态,是贡献与时间挂钩:设 f i , j , k , o p f_{i,j,k,op} fi,j,k,op 表示收集区间 [ i , j ] [i,j] [i,j] 的雕塑,收集了 k k k 个,收集完之后停在左或右端点,花费的最小时间。

因为在起点也可以顺时针和逆时针走,所以我们设破环成链之后的 n + 1 n+1 n+1 号点为起点,左圈逆时针为 n ∼ 1 n\sim 1 n1,右圈顺时针为 n + 2 ∼ 2 n + 1 n+2\sim 2n+1 n+22n+1

初始化 x n + 1 = L , t n + 1 = 0 x_{n+1}=L,t_{n+1}=0 xn+1=L,tn+1=0 f f f 极大值。

从一开始在起点(收集 k = 0 k=0 k=0 个雕塑时),就得先从起点走过去包含了 n + 1 n+1 n+1 的、期望的区间 [ i , j ] [i,j] [i,j] 的左或右端点了( i , j i,j i,j 分别在起点 n + 1 n+1 n+1 的左端右端,即 i ∈ [ 1 , n + 1 ] , j ∈ [ n + 1 , 2 n + 1 ] i\in[1,n+1],j\in[n+1,2n+1] i[1,n+1],j[n+1,2n+1]):
f i , j , 0 , 0 = L − a i f i , j , 0 , 1 = a j − L \begin{matrix} f_{i,j,0,0}=L-a_i\\ f_{i,j,0,1}=a_j-L \end{matrix} fi,j,0,0=Laifi,j,0,1=ajL

其实接下来和关路灯这道题大差不差了。不过这题多了分别考虑不取或者取雕塑。

不取的话直接从雕塑数为 k k k 的状态转移过来:
f i , j , k , 0 = min ⁡ { f i + 1 , j , k , 0 + ∣ x i + 1 − x i ∣ , f i + 1 , j , k , 1 + ∣ x j − x i ∣ } f i , j , k , 1 = min ⁡ { f i , j − 1 , k , 0 + ∣ x i − x j ∣ , f i , j − 1 , k , 1 + ∣ x j − 1 − x j ∣ } \begin{matrix} f_{i,j,k,0}=\min\{f_{i+1,j,k,0}+|x_{i+1}-x_i|,f_{i+1,j,k,1}+|x_j-x_i|\}\\ f_{i,j,k,1}=\min\{f_{i,j-1,k,0}+|x_i-x_j|,f_{i,j-1,k,1}+|x_{j-1}-x_j|\} \end{matrix} fi,j,k,0=min{fi+1,j,k,0+xi+1xi,fi+1,j,k,1+xjxi}fi,j,k,1=min{fi,j1,k,0+xixj,fi,j1,k,1+xj1xj}

取的话就从雕塑数为 k − 1 k-1 k1 的状态转移过来,不过要注意小于要求的时间节点:

  • f i , j , k , 0 = min ⁡ { f i + 1 , j , k − 1 , 0 + ∣ x i + 1 − x i ∣ , f i + 1 , j , k − 1 , 1 + ∣ x j − x i ∣ } f_{i,j,k,0}=\min\{f_{i+1,j,k-1,0}+|x_{i+1}-x_i|,f_{i+1,j,k-1,1}+|x_j-x_i|\} fi,j,k,0=min{fi+1,j,k1,0+xi+1xi,fi+1,j,k1,1+xjxi}
    可以转移当且仅当 min ⁡ { } \min\{\} min{} 内的项不大于 t i t_i ti,即取在 i i i 上的雕塑;
  • f i , j , k , 1 = min ⁡ { f i , j − 1 , k − 1 , 0 + ∣ x i − x j ∣ , f i , j − 1 , k − 1 , 1 + ∣ x j − 1 − x j ∣ } f_{i,j,k,1}=\min\{f_{i,j-1,k-1,0}+|x_i-x_j|,f_{i,j-1,k-1,1}+|x_{j-1}-x_j|\} fi,j,k,1=min{fi,j1,k1,0+xixj,fi,j1,k1,1+xj1xj}
    可以转移当且仅当 min ⁡ { } \min\{\} min{} 内的项不大于 t j t_j tj,即取在 j j j 上的雕塑。

然后统计答案,找到 k k k 最大的合法状态即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=402,inf=0x3f3f3f3f;
ll n,L,x[N],t[N];
ll f[N][N][N][2];
int main()
{scanf("%lld%lld",&n,&L);for(int i=1;i<=n;i++){scanf("%lld",&x[i]);x[i+n+1]=x[i]+L;}x[0]=0,x[n+1]=L;for(int i=1;i<=n;i++){scanf("%lld",&t[i]);t[i+n+1]=t[i];}memset(f,inf,sizeof(f));//起点是n+1 for(int j=n+1;j<=n+1+n;j++)//右 {for(int i=n+1;j<=i+n;i--)//左 {f[i][j][0][0]=L-x[i];//起点 向左 f[i][j][0][1]=x[j]-L;//起点 向右 }}for(int len=2;len<=n+1;len++)//成环 {for(int i=1;i<=n+1;i++)//左端点 {ll j=i+len-1;for(int k=1;k<len;k++){f[i][j][k][0]=min(f[i][j][k][0],min(f[i+1][j][k][0]+abs(x[i+1]-x[i]),f[i+1][j][k][1]+abs(x[j]-x[i])));f[i][j][k][1]=min(f[i][j][k][1],min(f[i][j-1][k][0]+abs(x[i]-x[j]),f[i][j-1][k][1]+abs(x[j-1]-x[j])));if(f[i+1][j][k-1][0]+abs(x[i+1]-x[i])<=t[i])//取i,i+1->i f[i][j][k][0]=min(f[i][j][k][0],f[i+1][j][k-1][0]+abs(x[i+1]-x[i]));if(f[i+1][j][k-1][1]+abs(x[j]-x[i])<=t[i])//取i,j->i f[i][j][k][0]=min(f[i][j][k][0],f[i+1][j][k-1][1]+abs(x[j]-x[i]));if(f[i][j-1][k-1][0]+abs(x[i]-x[j])<=t[j])//取j,i->jf[i][j][k][1]=min(f[i][j][k][1],f[i][j-1][k-1][0]+abs(x[i]-x[j]));if(f[i][j-1][k-1][1]+abs(x[j-1]-x[j])<=t[j])//取j,j-1->jf[i][j][k][1]=min(f[i][j][k][1],f[i][j-1][k-1][1]+abs(x[j-1]-x[j])); }}}ll ans=0;for(int len=2;len<=n+1;len++){for(int i=1;i<=n+1;i++){ll j=i+len-1;for(ll k=len;k>=1;k--){if(ans>=k)break;if(f[i][j][k][0]<inf||f[i][j][k][1]<inf){ans=max(ans,k);break;}}}}printf("%lld",ans);return 0;
}
http://www.xdnf.cn/news/1150.html

相关文章:

  • Spring Boot 应用优雅关闭
  • MYSQL—两阶段提交
  • 4.基础开发工具
  • stat判断路径
  • 【设计模式】深入解析代理模式(委托模式):代理模式思想、静态模式和动态模式定义与区别、静态代理模式代码实现
  • 基于PHP+MySQL实现(Web)单词助手网站
  • 基于javaweb的SSM+Maven教材管理系统设计与实现(源码+文档+部署讲解)
  • 深入理解 Java 中的 Classpath
  • 【Java面试笔记:基础】3.谈谈final、finally、 finalize有什么不同?
  • [Java] 泛型
  • Python 设计模式:享元模式
  • JVM虚拟机-类加载器、双亲委派模型、类装载的执行过程
  • 虚无隧穿产生宇宙(true nothing tunneling) 这个的真空是哪种
  • GitLab 提交权限校验脚本
  • 界面控件DevExpress WPF v25.1预览 - 支持Windows 11系统强调色
  • MuJoCo中的机器人状态获取
  • 第六篇:linux之解压缩、软件管理
  • Vue3集成sass
  • Unity 跳转资源商店,并打开特定应用
  • 滑动窗口学习
  • 【HTTPS协议原理】数据加密、如何防止中间人攻击、证书和签名、HTTPS完整工作流程
  • UnityDots学习(四)
  • 关于RPC
  • 图数据库nebula测试指南
  • 在 NVIDIA Orin (JetPack 6.0) 上安装 PyTorch 2.4 + Torchvision 0.19
  • 每日算法-250422
  • 几种Word转换PDF的常用方法
  • 如何在idea里创建注释模版
  • 真我推出首款 AI 翻译耳机,支持 32 种语言翻译
  • 拥抱健康生活,开启养生之旅