首页 > 其他分享 >CF704B Ant Man 题解

CF704B Ant Man 题解

时间:2024-09-05 20:36:34浏览次数:9  
标签:5010 填入 min 题解 后面 CF704B Ant long define

题目传送门

前置知识

预设性 DP

解法

考虑统计每个数单独的贡献,然后进行预设性 DP。

设 \(f_{i,j}\) 表示当前填了 \([1,i]\) 时有 \(j\) 个连续段的最小权值,边界为 \(f_{0,0}=0\)。

对 \(i(i \ne s,i \ne e)\) 填入的位置进行分讨。

  • 新开一段
    • 后面填入的数都比 \(i\) 大(如果存在后面填入的数的话,即 \(j>[i>s]+[i>t]\)),故 \(f_{i,j}=\min(f_{i,j},f_{i-1,j-1}-2x_{i}+b_{i}+d_{i})\)。
  • 连接到某个连续段的前后
    • 连接到某个连续段的前面(如果可以在前面的话,即 \(j>[i>s]\))时,后面填入的数(在 \(i\) 左面)比 \(i\) 大,而 \(i\) 右面的数比 \(i\) 小,故 \(f_{i,j}=\min(f_{i,j},f_{i-1,j}+b_{i}+c_{i})\)。
    • 连接到某个连续段的后面(如果可以在后面的话,即 \(j>[i>t]\))时,后面填入的数(在 \(i\) 右面)比 \(i\) 大,而 \(i\) 左面的数比 \(i\) 小,故 \(f_{i,j}=\min(f_{i,j},f_{i-1,j}+a_{i}+d_{i})\)。
  • 连接两个连续段
    • \(i\) 比旁边的两个数都要大,故 \(f_{i,j}=\min(f_{i,j},f_{i-1,j+1}+2x_{i}+a_{i}+c_{i})\)。

当 \(i=s\) 时只可能放到首端,可行的转移操作只有新开一段和连接到某个连续段的前面且前面不会再有数填,故 \(f_{i,j}=\min(f_{i-1,j-1}-x_{i}+d_{i},f_{i-1,j}+x_{i}+c_{i})\);当 \(i=e\) 时只可能放到末端,可行的转移操作只有新开一段和连接到某个连续段的后面且后面不会再有数填,故 \(f_{i,j}=\min(f_{i-1,j-1}-x_{i}+b_{i},f_{i-1,j}+x_{i}+a_{i})\)。

最终有 \(f_{n,1}\) 即为所求。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
ll f[5010][5010],x[5010],a[5010],b[5010],c[5010],d[5010];
int main()
{
	ll n,s,e,i,j;
	cin>>n>>s>>e;
	for(i=1;i<=n;i++)
	{
		cin>>x[i];
	}
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(i=1;i<=n;i++)
	{
		cin>>b[i];
	}
	for(i=1;i<=n;i++)
	{
		cin>>c[i];
	}
	for(i=1;i<=n;i++)
	{
		cin>>d[i];
	}
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
		{
			if(i==s)
			{
				f[i][j]=min(f[i][j],f[i-1][j-1]-x[i]+d[i]);
				f[i][j]=min(f[i][j],f[i-1][j]+x[i]+c[i]);
			}
			else
			{
				if(i==e)
				{
					f[i][j]=min(f[i][j],f[i-1][j-1]-x[i]+b[i]);
					f[i][j]=min(f[i][j],f[i-1][j]+x[i]+a[i]);
				}
				else
				{
					if(j>(i>s)+(i>e))
					{
						f[i][j]=min(f[i][j],f[i-1][j-1]-2*x[i]+b[i]+d[i]);
					}
					if(j>(i>s))
					{
						f[i][j]=min(f[i][j],f[i-1][j]+b[i]+c[i]);
					}
					if(j>(i>e))
					{
						f[i][j]=min(f[i][j],f[i-1][j]+a[i]+d[i]);
					}
					f[i][j]=min(f[i][j],f[i-1][j+1]+2*x[i]+a[i]+c[i]);
				}
			}
		}
	}
	cout<<f[n][1]<<endl;
	return 0;
}

标签:5010,填入,min,题解,后面,CF704B,Ant,long,define
From: https://www.cnblogs.com/The-Shadow-Dragon/p/18399200

相关文章

  • 洛谷 P1516 青蛙的约会 题解
    一道简单的数学题~首先分析题意。精简得出:假设跳了\(t\)次,那么青蛙A的坐标是\((x+mt)\modL\),青蛙B的坐标是\((y+nt)\modL\),列出方程:\[x+mt\equivy+nt\pmodL\]由于余数具有可减性,所以把\(y+nt\)移到左边,得出:\[x-y+mt-nt\equiv0\pmodL\]写成人话:\[(x-y+mt-nt)\mod......
  • 三星的MobileQuant:将高性能语言模型带到你的口袋中
    大型语言模型(LLMs)在语言处理方面取得了显著成果,并广泛应用于各种场景。然而,在移动设备(如手机)上实现LLMs存在许多挑战,特别是在内存、能耗和计算需求方面的限制。这些制约因素阻碍了LLMs在此类设备上的广泛应用。一种有前景的解决方案是减少权重和激活的位宽,使8位激活成为在设备......
  • 9.5 上午 becoder 模拟赛总结 & 题解
    T1文本编辑器说实话,看到题目的第一瞬间,我还以为gm第一道就放了平衡树。一道链表的模板题,当然愿意也可以用平衡树写,不多说了,直接放代码(100pts):#defineN1000005chars[N],t[N];intnow,pre[N],nxt[N];intmain(){scanf("%s%s",s+1,t+1);intn=strlen(s+1);......
  • 避免的10个关键Google Merchant Center错误
    作为一名电子商务商家,您可能已经了解使用GoogleMerchantCenter来管理产品数据并在Google服务(主要是Google购物)上展示商品的好处。然而,由于可用的功能和设置众多,您很容易陷入一些常见的陷阱,这些陷阱会损害您的销售和曝光度。别担心!在本文中,我们将讨论GoogleMerchantCenter......
  • 活动在即,不容错过丨亚信安慧AntDB诚邀您参加“PostgreSQL数据库技术峰会”
    ​​9月7日下午,“PostgreSQL数据库技术峰会”西安站将在西安市西安元谷学习中心4号厅举办。湖南亚信安慧科技有限公司(简称“亚信安慧”)受邀参会,将带来《提升企业数据安全,AntDB数据库回收站技术应用》的精彩演讲。在此,亚信安慧AntDB数据库诚邀您莅临参会,与业内专家共同探讨数据库技......
  • 【转载】P1399 [NOI2013] 快餐店 题解
    作者%%%%%%NightTide%%%%%%题目大意求一棵基环树的重心。即一个点,使得树上到其距离最长的点到其的距离最短。注意,这个点不一定是一个节点,可以在树上的任意位置。输出树上到其距离最长的点到其的距离。或者说求基环树最短的直径?(大雾解题思路显然,这颗基环树的直径只有两......
  • antD——报错:模块 ""antd/es/checkbox/Group"" 没有导出的成员 "CheckboxValueType"。
    参考:1. https://github.com/ant-design/ant-design/issues/50000  importtype{CheckboxValueType}from'antd/es/checkbox/Group'失效#500002. https://github.com/ant-design/ant-design/pull/49073  fix:fixCheckbox.Grouptype #490733. https://ant-de......
  • [USACO13OPEN] Photo G 题解
    前言题目链接:洛谷。题意简述一个长度为\(n\)的序列,有一些位置染了色。现给出\(m\)条限制,第\(i\)条限制为\(l_i\simr_i\)中有且仅有一个位置染色。求出满足这\(m\)中条件,染色位置个数最多为多少。\(n\leq2\times10^5\),\(m\leq10^5\)。题目分析方法\(1\):差......
  • Baby Ehab Plays with Permutations 题解
    前言题目链接:Codeforces;洛谷。题意简述你有一个长度为\(n\)的序列\(p\)满足\(p_i=i\),你可以进行\(x\)次操作,每次操作找到两个不同的\(i,j\)并且交换\(p_i,p_j\),问最终有几个可能的序列。分别求出\(x=1,\ldots,k\)时的答案。\(1\len\le10^9\),\(1\lek\le......
  • 洛谷 P2860 Redundant Paths G
    洛谷P2860RedundantPathsG题意给定一张图,求最少添加几条边使得原图变为边双连通图。思路先将原图进行边双连通分量缩点,因为已经边双连通的子图我们不用考虑。缩点后会得到一棵树,每一条边都是桥。假定有\(k\)个叶子节点。我们可以把叶子节点两个两个配对连边形成环,这样......