//这题本质还是一个背包问题
//怎么去思考这个问题呢
//我最开始的思想是根据经验来看，最小增量运算数，并且使数组变美丽，那么就有点像编辑距离的问题
//但是我看了下时间复杂度，不能是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(vector<int>& nums, int k) {
vector<vector<long long>> f(nums.size(),vector<long 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;
}
};
