fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define kiki INT_MAX
  3. #define tourist long long
  4. #define pb push_back
  5.  
  6.  
  7. using namespace std;
  8. const int maxn = 500008;
  9. double dp[maxn];
  10. //dp[0] = 0.5;
  11.  
  12.  
  13. //how to solve
  14. //duyet dp
  15. //tim len lowns nhat co the copy
  16. //doi chieu voi cai string hien tai
  17. //dp[i+1] = dp[i] + 0,5
  18. //dp[i+len] = dp[i]+1,5
  19. //dp[i] la gia tri to nhat
  20.  
  21.  
  22. void nirvana()
  23. {
  24.     freopen("test.inp", "r", stdin);
  25.     freopen("test.out", "w", stdout);
  26. }
  27.  
  28. void solve()
  29. {
  30.     string s;
  31.     cin>>s;
  32.     int n = s.size();
  33.     s = " " + s;
  34.     //int n = s.size() -1;
  35.    // string max_len = "";
  36.     //string l = "";
  37.     //bool ok  = false;
  38.  
  39.     dp[0] = 0;
  40.     for(int i =1; i<=n; i++)
  41.     {
  42.         dp[i] =maxn;
  43.     }
  44.     //for(int c: dp) cout<<c<<" "<<endl;
  45.     for(int i =  0 ;i<n ; i++)
  46.     {
  47.  
  48.         dp[i+1] = min(dp[i+1], dp[i]+0.5);
  49.         int x =1;
  50.         int y = i +1;
  51.  
  52.         while(x<=i && y<=n)
  53.         {
  54.             if(s[x ] == s[y])
  55.             {
  56.                 x++;
  57.                 y++;
  58.             }else break;
  59.         }
  60.  
  61.         dp[i+x - 1] = min(dp[i+x -1], dp[i]+1.5);
  62.     }
  63.     //cout<<dp[0]<<endl;
  64.     //cout<<dp[1]<<endl;
  65.     cout<<fixed<<setprecision(1)<<dp[n]<<endl;
  66.  
  67.     //qhd:
  68. }
  69.  
  70. int main()
  71. {
  72.     nirvana();
  73.     ios_base::sync_with_stdio(0);
  74.     cin.tie(0);
  75.     cout.tie(0);
  76.  
  77.     //testcase();
  78.     solve();
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2WNFtG
language:
C++ (gcc 8.3)
created:
1 day 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!