• Giải thích qua ý tưởng làm bài là như sau:
• Nếu độ dài của các thanh gỗ là rất rất lớn đi, mỗi thanh dài hơn 1e9, nhưng số lượng thanh gỗ tối đa cần dùng cũng chỉ là n. Vì mỗi ô ta để một độ dài thanh gỗ là 1*độ dài thích hợp là được.
• N là số lượng tối đa, vậy số lượng tối thiểu sẽ nhỏ hơn n. Vậy bây giờ ta hỏi khi nào thì sẽ giảm đáp án từ n đi 1 còn n-1.
• Đó là khi có 2 thanh gỗ có độ dài bằng nhau và ở giữa không có thanh nào thấp hơn nó.
• Ví dụ có 4 thanh gỗ là [8, 1000, 99, 8], thì đáp án là 3. Bởi vì ta để 4 * 8 [chạy từ 1 tới 4], thanh gỗ 2 * 91 [chạy từ 2 tới 3], thanh gỗ 1 * 9-1 chạy từ [2 tới 2].
• Hãy thử lấy thêm ví dụ khác rồi thử tìm đáp án tối ưu. [5, 8, 5, 2], [8, 5, 8, 2], [5, 6, 7, 8], [5, 6, 7, 8, 6], [5, 6, 7, 8, 6, 1, 2, 3, 4, 5, 6, 2, 8]...
• Khi tham gia lập trình thi đấu thì chỉ cần nhận xét được sự thay đổi của đáp án, và lên ý tưởng làm bài, tiếp đó là code theo ý tưởng là sẽ ac. (ý tưởng phải đúng đã nha)

Code

/**
  * Create: Wednesday 2022-08-10-10.16.56 GMT+7
  * Title : Rectangle Blocks 2
  * Author:
*****/


#include <bits/stdc++.h>

using namespace std;

int main() {
   ios_base::sync_with_stdio (0); cin.tie (0);

   #define int long long


   int n; cin >> n;

   vector <int> a(n);
   for(int i=0; i<n; ++i){
      cin >> a[i];
   }


   deque <int> d;
   d.push_back(0);

   int cnt=0;
   for(int i=0; i<n; ++i){

      for( ;d.back()>a[i]; ){
         d.pop_back();
      }

      if(a[i]==d.back()){
         cnt+=1;
      }
      else{
         d.push_back(a[i]);
      }
   }


   int ans = n-cnt;

   cout <<ans <<endl;











   return 0;
}