fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define F first
  4. #define S second
  5. const int N = 1000 + 5;
  6.  
  7. int n;
  8. string s;
  9. int dp[N][N];
  10.  
  11. bool Compare(int x, int y, int u, int v) // kiểm tra số được tạo bởi đoạn [x, y] có lớn hơn đoạn [u, v] hay không
  12. {
  13.     if(y - x != v - u) return (y - x > v - u); // nếu độ dài không bằng nhau thì có thể so sánh ngay
  14.     for(int i = 0; i <= y - x; i++)
  15.         if(s[x + i] != s[u + i]) return s[x + i] > s[u + i];
  16.     return 0;
  17. }
  18.  
  19. int main() 
  20. {
  21.     cin.tie(0) -> sync_with_stdio(0);
  22.     cin >> n;
  23.     cin >> s;
  24.     s = " " + s;
  25.     int res = 0;
  26.     for(int i = 1; i <= n; i++)
  27.     {
  28.         for(int len = 1; len <= i; len++) 
  29.         {
  30.             int l = i - len + 1, r = i;
  31.             if(s[l] == '0') // xử lý trường hợp số 0 ở đầu
  32.             {
  33.                 if(len == 1) dp[i][len] = 1;
  34.                 else continue;
  35.             }
  36.             for(int j = 0; j < l; j++) // tính quy hoạch động
  37.             {
  38.                 int l2 = max(j - len + 1, 1), r2 = j;
  39.                 if(Compare(l, r, l2, r2))
  40.                     dp[i][len] = max(dp[i][len], dp[j][len] + 1);
  41.                 else
  42.                     dp[i][len] = max(dp[i][len], dp[j][len - 1] + 1);
  43.                 res = max(res, dp[i][len]);
  44.             }
  45.         }
  46.         for(int len = 1; len <= n; len++) // max tiền tố
  47.             dp[i][len] = max(dp[i][len], dp[i][len - 1]);
  48.     }
  49.     cout << res;
  50.  
  51. 	return 0;
  52. }
  53.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/U2coRi
language:
C++14 (clang 8.0)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!