minimum deletion to make wave array ??

Правка en1, от ayandutt2002, 2022-06-15 13:19:27

given an array what is the minimum no of integers to be removed to make the array wave-like; n<=1000; can anyone help me with the approach of the question?? my solution class Solution { public: int minimumMountainRemovals(vector& nums) { int n=nums.size(); vector<vector>dp(n,vector(2,1001)); dp[0][0]=dp[0][1]=0; int ans=INT_MAX; for(int i=1;i<n;i++){ for(int j=i-1;j>=0;j--){ if(nums[j]<nums[i]){ dp[i][0]=min(dp[i][0],dp[j][1]+(i-j-1)); }else if(nums[j]>nums[i]){ dp[i][1]=min(dp[i][0],dp[j][0]+(i-j-1)); } } if(dp[i][0]>1001)dp[i][0]=(i); if(dp[i][1]>1001)dp[i][1]=(i); ans=min(ans,min(dp[i][0],dp[i][1])+(n-1-i)); }

return ans;
}

}; can this work or not please help me!!

Теги dp, acm-icpc, algorithms

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский ayandutt2002 2022-06-15 13:21:28 726
en1 Английский ayandutt2002 2022-06-15 13:19:27 977 Initial revision (published)