Category Archives: Longest Common Subsequence

(LightOj) 1033 – Generating Palindromes

0
Posted on by 
//link: http://lightoj.com/volume_showproblem.php?problem=1033

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl

using namespace std;

#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;
struct ASDFG{
    template<typename T>
    ASDFG& operator,(vector<T> &v){
        pf("[");
        cout<<v[0];
        FOR(i, 1, SZ(v)){
            cout<<", "<<v[i];
        }
        pf("]");
        return *this;
    }

    template<typename T>
    ASDFG& operator,(T x) {
        cout<<x<<" ";
        return *this;
    }


}asdfg;



//Header ends here
#define MAXX 102

char str[MAXX];

int dp[MAXX][MAXX];
int len;


int min_cost(int i, int j)
{
    if(i < 0) return len - j;
    if(j >= len) return i+1;

    int &ret = dp[i][j];
    if(ret != -1) return ret;


    if(str[i] == str[j])
    {
        return ret = min_cost(i-1, j+1);
    }
    else
    {
        return ret = 1 + min( min_cost(i-1, j), min_cost(i, j+1) );
    }

}



int main()
{
    int kases, kaseno = 0;
    take(kases);



    while(kases--)
    {
        scanf("%s", str);
        len = strlen(str);
        mem(dp, -1);
        int res = 1<<29;
        for(int i=0; i<len-1; i++)
        {
            res = min( res, min_cost(i, i) );
            res = min(res, min_cost(i, i+1));
        }
        pf("Case %d: %d\n", ++kaseno, len==1?0:res);
    }

}

Another solution using LCS directly


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>


#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) FOR(i, 0, n)
#define sf scanf
#define pf printf
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define ll long long
#define dd double
#define all(v) v.begin(), v.end()
#define PI acos(-1.0)
#define mem(ara, value) memset(ara, value, sizeof(ara))
#define paii pair<int, int>
#define pall pair<ll, ll>
#define SZ(a) int(a.size())
#define read(nm) freopen(nm, "r", stdin)
#define write(nm) freopen(nm, "w", stdout)
#define dump(x) cout<<#x<<" = "<<x<<endl

using namespace std;

#define take(args...) asdf,args
#define debug(args...) asdfg,args; cout<<endl
struct ASDF{
    ASDF& operator,(int &a) {
        sf("%d", &a);
        return *this;
    }
    ASDF& operator,(long int &a){
        sf("%ld", &a);
        return *this;
    }
    ASDF& operator,(long long int &a){
        sf("%lld", &a);
        return *this;
    }
    ASDF& operator,(char &c){
        sf("%c", &c);
        return *this;
    }
    ASDF& operator,(double &d){
        sf("%lf", &d);
        return *this;
    }

    template<typename T>
    ASDF& operator,(T &a){
        cin>>a;
        return *this;
    }
}asdf;
struct ASDFG{
    template<typename T>
    ASDFG& operator,(vector<T> &v){
        pf("[");
        cout<<v[0];
        FOR(i, 1, SZ(v)){
            cout<<", "<<v[i];
        }
        pf("]");
        return *this;
    }

    template<typename T>
    ASDFG& operator,(T x) {
        cout<<x<<" ";
        return *this;
    }


}asdfg;



//Header ends here
#define MAXX 102

char str[MAXX];

int dp[MAXX][MAXX];
int len;

int LCS(int i, int j)
{
    if(i<0 || j>=len) return 0;
    int &ret = dp[i][j];
    if(ret != -1) return ret;

    if(str[i] == str[j]) return ret = 1 + LCS(i-1, j+1);
    return ret = max(LCS(i-1, j), LCS(i, j+1));
}




int main()
{
    int kases, kaseno = 0;
    take(kases);



    while(kases--)
    {
        scanf("%s", str);
        len = strlen(str);
        mem(dp, -1);
        int res = 1<<29;
        for(int i=0; i<len-1; i++)
        {
            res = min(res, len+1 - 2*LCS(i, i));
            res = min(res, len - 2*LCS(i, i+1));
        }

        pf("Case %d: %d\n", ++kaseno, len==1?0:res);
    }

}

(UVa) 10635 – Prince and Princess

0
Posted on by 
/*
user: php
time: 0.040 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1576
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf

using namespace std;

#define MAXX 251

int tmp, sc[MAXX*MAXX];
int n, p, q;
int pos[MAXX*MAXX];

int LIS()
{
    int I[MAXX*MAXX + 1];
    I[0] = -INF;

    FOR(i, 1, q)
    {
        I[i] = INF;
    }

    int LisLength = 0;
    loop(i, q)
    {
        int low, high, mid;
        low = 0;
        high = LisLength;

        while(low <= high)
        {
            mid = (low+high)/2;
            if(I[mid] < sc[i])
            {
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
        I[low] = sc[i];
        if(LisLength < low)
        {
            LisLength = low;
        }
    }
    return LisLength;

}

int main()
{
    int kases, kaseno = 0;
    getint(kases);
    while(kases--)
    {
        getint(n); getint(p); getint(q);
        p++;
        q++;

        mem(pos, -1);

        loop(i, p)
        {
            getint(tmp);
            pos[tmp] = i+1;
        }

        loop(i, q)
        {
            getint(tmp);
            sc[i] = pos[tmp] - 1;

        }

        pf("Case %d: %d\n", ++kaseno, LIS() );

    }

    return 0;
}

(UVa) 10192 – Vacation

0
Posted on by 
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1133
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define pf printf
#define sf scanf

using namespace std;

#define MAXX 102

char frst[MAXX], scnd[MAXX];
int dp[MAXX][MAXX];
int frlen, sclen;

int rec(int i, int j)
{
    if(i>=frlen || j>=sclen) return 0;
    int &ret = dp[i][j];
    if(ret != -1) return ret;

    if( frst[i] == scnd[j] )
    {
        return ret = 1 + rec(i+1, j+1);
    }
    else
    {
        return ret = max(rec(i, j+1), rec(i+1, j));
    }
}



int main()
{
    int kaseno = 0;
    while(true)
    {
        gets(frst);
        frlen = strlen(frst);
        if(frst[0] == '#' && frlen == 1)
        {
            break;
        }
        gets(scnd);
        sclen = strlen(scnd);

        mem(dp, -1);
        pf("Case #%d: you can visit at most %d cities.\n", ++kaseno, rec(0, 0));




    }


    return 0;
}

(UVa) 10066 – The Twin Towers

0
Posted on by 
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1007
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define pf printf
#define sf scanf

using namespace std;


int frstln, scndln;
int frstrad[102];
int scndrad[102];
int dp[102][102];

int rec(int i, int j)
{
    if(i >= frstln || j >= scndln) return 0;
    int &ret = dp[i][j];
    if(ret != -1) return ret;


    if(frstrad[i] == scndrad[j])
    {
        return ret = 1 + rec(i+1, j+1);
    }
    else
    {
        return ret = max(rec(i+1, j), rec(i, j+1));
    }
}





int main()
{
    int kaseno = 0;
    while(true)
    {
        getint(frstln); getint(scndln);
        if(frstln == 0 && scndln == 0) break;
        loop(i, frstln)
        {
            getint(frstrad[i]);
        }
        loop(i, scndln)
        {
            getint(scndrad[i]);
        }

        mem(dp, -1);

        pf("Twin Towers #%d\n", ++kaseno);
        pf("Number of Tiles : %d\n\n", rec(0, 0));




    }

    return 0;
}

(UVa) 10405 – Longest Common Subsequence

0
Posted on by 
/*
user: php
time: 0.056 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1346
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)

using namespace std;

#define MAXX 1001

int first_len, second_len;

int dp[MAXX][MAXX];
char str1[MAXX], str2[MAXX];



int LCS(int i, int j)
{
    if(i == first_len || j == second_len ) return 0;

    int &ret = dp[i][j];
    if( ret != -1 ) return ret;

    if(str1[i] == str2[j])
    {
        return ret = 1 + LCS(i+1, j+1);
    }

    return ret = max(LCS(i+1, j), LCS(i, j+1));

}


int main()
{




    while(gets(str1))
    {
        gets(str2);
        first_len = strlen(str1);
        second_len = strlen(str2);

        mem(dp, -1);

        printf("%d\n", LCS(0, 0));





    }

    return 0;
}