Dynamic-Programming/MinString(DP).cpp at master · robinrst/Dynamic-Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include        "algorithm"
#include        "iostream"
#include        "numeric"
#include        "iomanip"
#include        "cstring"
#include        "math.h"
#include        "bitset"
#include        "string"
#include        "vector"
#include        "ctime"
#include        "queue"
#include        "stack"
#include        "map"
#include        "set"

#include        "ext/pb_ds/assoc_container.hpp" // Common file
#include        "ext/pb_ds/tree_policy.hpp" // Including tree_order_statistics_node_update
#include        "ext/pb_ds/detail/standard_policies.hpp"

using namespace std;
using namespace __gnu_pbds;


#define          f first
#define          lgn 25
#define          endl '\n'
#define          sc second
#define          pb push_back
#define          N (int) 200+5
#define          PI acos(-1.0)
#define          int long long
#define          vi vector<int>
#define          mod 1000000007
#define          ld long double
#define          eb emplace_back
#define          mii map<int,int>
#define          vpii vector<pii>
#define          pii pair<int,int>
#define          pq priority_queue
#define          BLOCK (int)sqrt(N)
#define          test(x) while(x--)
#define          all(x) begin(x),end(x)
#define          allr(x) x.rbegin(),x.rend()
#define          fo(i,a,n) for(int i=a;i<n;i++)
#define          rfo(i,n,a) for(int i=n;i>=a;i--)
#define          FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define          time() cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n"
#define            bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)

typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update >
OS ;

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;

int n,m,k,q;
string s;
int dp[N][N]; // dp[i][j] -> denotes minimum length we can construct by changing in interval (i,j)
int val[N][N]; // val[i][j] -> It is used since if we get (a,b) then we can change it to c
               // and let suppose a -> 1st index and b-> 2nd index , so now val[1][2] will be c

void go()
{
     cin >> s;
     n = s.size();
     s = " " + s;

     memset( dp , 0, sizeof dp );
     memset( val , 0 , sizeof val );

     for( int i  = 1; i <= n; i++)
     {
          for( int j = i; j <= n; j++)
          {
               if( i == j )
               {
                    if( s[i] == 'a' ) val[i][i] = 1;
                    if( s[i] == 'b' ) val[i][i] = 2;
                    if( s[i] == 'c' ) val[i][i] = 3;
               }
               dp[i][j] = ( j - i + 1);
          }
     }

     for(int gap = 1; gap <= n; gap++)
     {
          for( int i = 1; i + gap <= n; i++)
          {
               int j = i + gap;

               for( int k = i; k < j; k++)
               {
                    dp[i][j] = min( dp[i][j] , dp[i][k] + dp[k+1][j] );

                    int sum = val[i][k] + val[k+1][j];

                    if( val[i][k] and val[k+1][j] and val[i][k] != val[k+1][j] and dp[i][j] > 0) // if values are different then we can reduce the length
                    {
                         if( sum == 3 ) val[i][j] = 3; // here we get ( 1,2) or (2 ,1), so we change it to -> 3
                         if( sum == 4 ) val[i][j] = 2; // here we get ( 1,3) or (3 ,1), so we change it to -> 2
                         if( sum == 5 ) val[i][j] = 1; // here we get ( 3,2) or (2 ,3), so we change it to -> 1

                         dp[i][j] = min( dp[i][j] , max(1LL , dp[i][j] - 1) ); // either the answer is (i,k) + (k+1,j)
                                                                              // which we have already calculated before finding sum
                                                                             // so now the length will reduce by 1 , so to avoid zero length max is used
                    }
               }

          }
     }

     cout << dp[1][n] << endl;

}

int32_t main()
{
     FAST;
     int t=1;
     cin>>t;
     test(t) go();
}