首页 > 其他分享 >美团笔试(2022.08.20)拟合

美团笔试(2022.08.20)拟合

时间:2022-08-20 20:12:53浏览次数:69  
标签:tmp 20 int 美团 数组 2022.08 操作 include dp

主要参考:牛客上分享的帖子以及力扣第72题编辑距离的题解

首先用动态规划做是最合适的

阶段:对A操作i次,对B操作j次

确定dp数组的含义:从数组A【0-i】到与数组B【0-j】保持一致所需要的操作次数

dp[i][j]

初始化: dp[i][0] : 从数组A【0-i】到与数组B【0】保持一致所需要的最小操作时间 即每次都只需要操作A【i】,dp[i][0]=dp[i-1][0]+abs(A[i-1]);
dp[0][j]: 从数组A【0-i】到与数组B【0】保持一致所需要的最小操作时间 即每次都只需要操作B【i】,dp[0][j]=dp[0][j-1]+abs(B[j-1]);

最终代码:

#include <iostream>
#include <vector>
#include <string> 
using namespace std;

int main()
{
	vector<int> a,b;
	int n,m,max;
	cin >> n;
	cin >> m;
	for(int i = 0; i<n;i++) 
	{
		int tmp = 0;
		cin >> tmp; 
		a.push_back(tmp);
	}
	for(int i = 0; i<m;i++) 
	{
		int tmp = 0;
		cin >> tmp;
		b.push_back(tmp);
	}
	vector<vector<int>> dp(n+1,vector<int>(m+1,0));
	for(int i = 1;i<n+1;i++)
	{
		dp[i][0] = dp[i-1][0]+ abs(a[i-1]);
	}
	for(int j = 1;j<m+1;j++)
	{
		dp[0][j] = dp[0][j-1]+ abs(b[j-1]);
	}
	for(int i = 1;i<n+1;i++)
	{
		for(int j=1;j<m+1;j++)
		{
			if(a[i-1]==b[j-1]) dp[i][j] = dp[i][j];
			else
			{
				dp[i][j]= min(dp[i-1][j]+abs(a[i-1]),min(dp[i][j-1]+abs(b[j-1]),dp[i-1][j-1]+abs(a[i-1]-b[j-1])));
			 } 
		}
	}
	cout << dp[n][m] <<endl;
	return 0;
 } 

看完大神的解释和自己写一遍之后又更加理解dp数组与存储数据的数组不是一个东西。
一定要先明确dp数组的含义才能进行动态规划。

标签:tmp,20,int,美团,数组,2022.08,操作,include,dp
From: https://www.cnblogs.com/black-worrior-2000/p/16608502.html

相关文章

  • 2022 PRML Stock Prediction
    关于RNN(循环神经网络)(简略了解): https://zhuanlan.zhihu.com/p/105383343关于LSTM(长短期记忆网络)以及GRU:Q1:LSTM如何实现长短期记忆?(《百面深度学习》p54)一般的RNN(循......
  • "蔚来杯"2022牛客暑期多校训练营4 N-Particle Arts
    问题描述InaconfinedNIOspace,therearennnNIOparticles,theiii-thofwhichhasaia_iai​jouleenergy.TheNIOparticlesareveryspecialastheykeep......
  • [题解] Codeforces 1720 E Misha and Paintings 结论
    算是诈骗题?令一开始就存在的颜色数为cnt。k>=cnt的情况,显然每次找一个出现不止一次的颜色,然后把这个颜色的恰好一个方块替换成一种没有出现过的颜色就可以了,\(k-cnt\)次解......
  • Ubuntu安装abaqus2022总结
    1.网上下载的安装包解压后好多文件在linux下没有执行权限,会导致安装失败。可以一次性使用 chmod-R+x./ 命令添加或者遇到一个添加一个。2.isight的安装过程脚本使用......
  • "蔚来杯"2022牛客暑期多校训练营3 C-Concatenation
    问题描述NIOwasthekingoftheOINKingdom.HehadNNNchildrenandwantedtoteachthemhowtocount.IntheOINKingdom,pentalisusedincounting,sohis......
  • "蔚来杯"2022牛客暑期多校训练营2 G-Link with Monotonic Subsequence
    问题描述First,let'sreviewsomedefinitions.Feelfreetoskipthispartifyouarefamiliarwiththem.Asequence aaaisanincreasing(decreasing)subsequ......
  • Bridge 2022 for Mac(br 2022文件管理软件)中文版
    Bridge2021forMac是一款组织工具应用,从AdobeBridge2021中可以查看、搜索、排序、管理和处理图像文件,还可以使用AdobeBridge2021mac中文版来创建新文件夹、对......
  • Adobe Bridge 2022(Br2022)mac/win
    AdobeBridge 是AdobeCreativeSuite的控制中心。您使用它来组织、浏览和寻找所需资源,用于创建供印刷、网站和移动设备使用的内容。AdobeBridge使您可以方便地访问本......
  • 使用docker简单编译k20pro内核
    简介本文将介绍一下如何使用docker编译红米k20pro的内核。作者当时尝试构建内核的原因是为了将3年前(好像是吧)购买的k20pro至尊版(已退役,12GB内存,512GB硬盘)制作成一个小的服......
  • JAVA基础--类型转换--2022年8月20日
    第一节1、为什么要进行类型转换存在不同类型的变量给赋值给其他类型的变量2、自动类型转换是什么样的类型范围小的变量,可以直接赋值给类型范围大的变量 第......