北京宏福建设工程有限公司网站,免费看国际短视频软件,怎么选择做网站的公司,厦门网站建设公司首选乐振//这题本质还是一个背包问题 //怎么去思考这个问题呢 //我最开始的思想是根据经验来看#xff0c;最小增量运算数#xff0c;并且使数组变美丽#xff0c;那么就有点像编辑距离的问题 //但是我看了下时间复杂度#xff0c;不能是n^2,那么再去仔细思… //这题本质还是一个背包问题 //怎么去思考这个问题呢 //我最开始的思想是根据经验来看最小增量运算数并且使数组变美丽那么就有点像编辑距离的问题 //但是我看了下时间复杂度不能是n^2,那么再去仔细思考一下看到该数组是美丽的并且美丽的代价是 //长度大于等于3的连续任意子数组是美丽的就是正确的我们从长度大于等于3这里桌上 //一定要知道长度大于等于3这个是这题的关键解决点 //那么根据动态规划的思想先去从前往后推导 //惊奇的发现这道题有点像背包问题dp和状态机dp //那么我们可以状态定义一下试一下 //f[i][0]表示从前i个物品当中选出物品并且第i个物品没有选且是美丽的 //f[i][1]表示从前i个物品当中选出物品并且第i个物品没有选且是美丽的 //假设当前是第i个 //那么能转移到第i个的可以由那几个状态转移并推导到当前第i位时的状态 //第i - 3个,i - 2个,i - 1个可以推导过来 //1.如果是第i - 3推导过来的话(并且是选了第 i- 3这个物品) // 那么当前第i位一定要选如果不选的话就不能成为美丽数组 // 如果第i - 3位没选的话那么不能从i - 3位转移到第i位 //那么第i - 3个转到第i个的状态转移方程就是 //f[i][1] max(0,k - a[i]) f[i - 3][1] //最开始错了一次我是都初始化成了0x3f3f3f3f但是这样会导致状态转移很麻烦因为这样还得判断 //是否前面的状态是0x3f3f3f3f索性我就让他转变成0就行(如果该点大于的话) //2.如果是第i - 2个转移到第i个的话 // 那么第i个可以分为选或不选 // 第i个选的话那么可以从第i - 2个不选和第i - 2个选表示出来 // f[i][1] f[i - 2][1] max(0,k - a[i]); // f[i][0] f[i - 2][1]; //第i - 1个同理 class Solution {
public:long long minIncrementOperations(vectorint nums, int k) {vectorvectorlong long f(nums.size(),vectorlong long(2,0));//这题本质还是一个背包问题//怎么去思考这个问题呢//我最开始的思想是根据经验来看最小增量运算数并且使数组变美丽那么就有点像编辑距离的问题//但是我看了下时间复杂度不能是n^2,那么再去仔细思考一下看到该数组是美丽的并且美丽的代价是//长度大于等于3的连续任意子数组是美丽的就是正确的我们从长度大于等于3这里桌上//一定要知道长度大于等于3这个是这题的关键解决点//那么根据动态规划的思想先去从前往后推导//惊奇的发现这道题有点像背包问题dp和状态机dp//那么我们可以状态定义一下试一下//f[i][0]表示从前i个物品当中选出物品并且第i个物品没有选且是美丽的//f[i][1]表示从前i个物品当中选出物品并且第i个物品没有选且是美丽的//假设当前是第i个//那么能转移到第i个的可以由那几个状态转移并推导到当前第i位时的状态//第i - 3个,i - 2个,i - 1个可以推导过来//1.如果是第i - 3推导过来的话(并且是选了第 i- 3这个物品)// 那么当前第i位一定要选如果不选的话就不能成为美丽数组// 如果第i - 3位没选的话那么不能从i - 3位转移到第i位//那么第i - 3个转到第i个的状态转移方程就是//f[i][1] max(0,k - a[i]) f[i - 3][1] //最开始错了一次我是都初始化成了0x3f3f3f3f但是这样会导致状态转移很麻烦因为这样还得判断//是否前面的状态是0x3f3f3f3f索性我就让他转变成0就行(如果该点大于的话)//2.如果是第i - 2个转移到第i个的话// 那么第i个可以分为选或不选// 第i个选的话那么可以从第i - 2个不选和第i - 2个选表示出来// f[i][1] f[i - 2][1] max(0,k - a[i]);// f[i][0] f[i - 2][1];//第i - 1个同理for(int i 0; i nums.size();i)if(nums[i] k)//初始化避免加上已经大于等于k的值{f[i][0] 0x3f3f3f3f; }f[0][1] max(0,k - nums[0]);//这个本质是这样的k nums[0] ? k-nums[0] : 0;但是我们这里提供一个比较简单的方法f[1][1] max(0,k - nums[1]);f[2][1] max(0,k - nums[2]);int n nums.size();for(int i 3; i n; i){f[i][1] min(min(f[i-3][1],f[i-2][1]),f[i-1][1])max(0,k-nums[i]);f[i][0] min(f[i-2][1],f[i-1][1]);}long long ans 1e14;for(int i n - 3;i n;i){//ans min(ans,min(f[i][1],f[i][0]));//答案不能这么写因为我们是判断最后3位哪个选最大值//选了后面就不用加了ans min(ans,f[i][1]);}return ans;}
};
