fork download
copy 
  1. /*
  2.     Author: NgThi Thao Duyen
  3.     Link submit: 
  4. */
  5.  
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8. #define ll long long 
  9. #define task "strdel"
  10. #define fi first
  11. #define se second
  12. #define pii pair<int,int>
  13. #define pb push_back
  14. #define dou double
  15. #define el '\n'
  16. #define ull unsigned long long 
  17. #define pll pair<ll,ll>
  18. const int maxN = 305;  // Sửa từ maxM = 300
  19. const int LIM = 1e9;
  20. const ll oo = 1e18;
  21. const int mod = (int)1e9+7;
  22. const int LOG = 23;
  23. string s;
  24. int T;
  25. int dp[maxN][maxN];
  26.  
  27. void solve()
  28. {
  29.     cin >> s;
  30.     int n = (int)s.length();
  31.     s = " " + s;
  32.  
  33.     // Khởi tạo
  34.     for(int i=1; i<=n; i++) {
  35.         for(int j=1; j<=n; j++) {
  36.             dp[i][j] = 0;
  37.         }
  38.     }
  39.  
  40.     for(int i=1; i<=n; i++) dp[i][i] = 1;
  41.  
  42.     for(int len=2; len<=n; len++)
  43.     {
  44.         for(int l=1; l<=n-len+1; l++)
  45.         {
  46.             int r = l+len-1;
  47.  
  48.             // Trường hợp cơ bản: xóa từng ký tự
  49.             dp[l][r] = 1 + dp[l+1][r];
  50.  
  51.             // Nếu s[l] == s[r], có thể xóa cùng lúc với phần bên trong
  52.             if(s[l] == s[r]) {
  53.                 if(len == 2) {
  54.                     dp[l][r] = 1;
  55.                 } else {
  56.                     dp[l][r] = min(dp[l][r], dp[l+1][r-1]);
  57.                 }
  58.             }
  59.  
  60.             // Tách xâu thành 2 phần
  61.             for(int k=l; k<r; k++) {
  62.                 dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r]);
  63.             }
  64.         }
  65.     }
  66.  
  67.     cout << dp[1][n] << el;
  68. }
  69.  
  70. int main()
  71. {
  72.     ios_base::sync_with_stdio(0); cin.tie(0);
  73.     if(fopen(task".inp","r"))
  74.     {
  75.         freopen(task".inp","r",stdin);
  76.         freopen(task".out","w",stdout);
  77.     }
  78.     cin >> T;
  79.     while(T--) solve();
  80.     return 0;
  81. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Grt0xz
language:
C++ (gcc 8.3)
created:
2 days 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!