hdu 1159dp lcs nlogn 해법

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<string>
#include<cmath>
#include<deque>
#include<map>
#include<queue>
#define iinf 0x7f7f7f7f
#define linf 1000000000000000000LL
#define dinf 1e200
#define eps 1e-11
#define lng long long
#define sqr(a) ((a)*(a))
#define pii pair<int,int>
#define X first
#define Y second
#define pi 3.14159265359
#define cc(i,j) memset(i,j,sizeof(i))
#define two(x)          ((lng)1<<(x))
#define mod  9901
#define pmod(x,y) (x%y+y)%y
using namespace std;
typedef vector<int>  vi;
typedef vector<string>  vs;
template<class T> inline void checkmax(T &x,T y){if(x<y) x=y;}
template<class T> inline void checkmin(T &x,T y){if(x>y) x=y;}
template<class T> inline T Min(T x,T y){return (x>y?y:x);}
template<class T> inline T Max(T x,T y){return (x<y?y:x);}
template<class T> T Abs(T a){return a>0?a:(-a);}
char a[11111],b[11111];
int dp[2000][2000];
int main()
{
     while(scanf("%s %s",a+1,b+1)==2)
     {
         int na=strlen(a+1),nb=strlen(b+1);
          cc(dp,0);
         for(int i=1;i<=na;++i)
        for(int j=1;j<=nb;++j)
          dp[i][j]=Max(dp[i-1][j-1]+(a[i]==b[j]),Max(dp[i-1][j],dp[i][j-1]));
          printf("%d
",dp[na][nb]);
     }
    return 0;
}

먼저 폭력을 행사한 이 문제는 감히 나에게 데이터량을 알려줄 수 있겠는가
다음은 nlogn입니다.

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<string>
#include<cmath>
#include<deque>
#include<map>
#include<queue>
#define iinf 0x7f7f7f7f
#define linf 1000000000000000000LL
#define dinf 1e200
#define eps 1e-11
#define lng long long
#define sqr(a) ((a)*(a))
#define pii pair<int,int>
#define X first
#define Y second
#define pi 3.14159265359
#define cc(i,j) memset(i,j,sizeof(i))
#define two(x)          ((lng)1<<(x))
#define mod  9901
#define pmod(x,y) (x%y+y)%y
using namespace std;
typedef vector<int>  vi;
typedef vector<string>  vs;
template<class T> inline void checkmax(T &x,T y){if(x<y) x=y;}
template<class T> inline void checkmin(T &x,T y){if(x>y) x=y;}
template<class T> inline T Min(T x,T y){return (x>y?y:x);}
template<class T> inline T Max(T x,T y){return (x<y?y:x);}
template<class T> T Abs(T a){return a>0?a:(-a);}
char a[11111],b[11111];
int g[11444],s[11444];
int main()
{
     while(scanf("%s %s",a+1,b+1)==2)
     {
         int na=strlen(a+1),nb=strlen(b+1);
         int y=0;
         vi p[26];
         for(int i=nb;i>=1;--i)
         p[b[i]-'a'].push_back(i);
         for(int i=1;i<=na;++i)
         for(int j=0,z=p[a[i]-'a'].size();j<z;++j)
         s[++y]=p[a[i]-'a'][j];
        cc(g,0x7f);
        int ans=0;
        for(int i=1;i<=y;++i)
        {
            int k=lower_bound(g+1,g+y+1,s[i])-g;
            checkmax(ans,k);
            g[k]=s[i];
        }
        printf("%d
",ans);
     }
    return 0;
}