2016年10月

题意:LCS。

$$ dp[i][j] = \begin{cases} max(dp[i-1][j], dp[i][j-1]), & S[i] \neq T[j] \\\\ dp[i-1][j-1]+1, & S[i]=T[j] \end{cases} $$

码(5096K, 32ms)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1e3 + 100;
char s[maxn], t[maxn];
int dp[maxn][maxn] = {0};
int main()
{
    while(~scanf("%s%s", s, t))
    {
        memset(dp, 0, sizeof dp);
        int slen = strlen(s), tlen = strlen(t);
        for(int i = 1; i <= slen; i++)
            for(int j = 1; j <= tlen; j++)
            {
                if(s[i - 1] == t[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); 
            }
        printf("%d\n", dp[slen][tlen]);
    }
    return 0;
}