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
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[2105][2105];
int f[2015][2105];
int main(){
    //freopen("testcase", "r", stdin);
    //freopen("out", "w", stdout);
    string s1, s2;
    cin >> s1 >> s2;
    for (size_t i = 0; i != s1.size(); i++){
        for (size_t j = 0; j != s2.size(); j++){
            if (s1[i] != s2[j]) f[i + 1][j + 1] = 0;
            else f[i + 1][j + 1] = f[i][j] + 1;
        }
    }
    for (size_t i = 0; i != s1.size(); i++){
        for (size_t j = 0; j != s2.size(); j++){
            a[i + 1][j + 1] = max(a[i + 1][j], a[i][j + 1]);
            if (f[i + 1][j + 1] == 3){
                a[i + 1][j + 1] = max(a[i+1][j+1],a[i - 2][j - 2] + 3);
            }
            else if (f[i + 1][j + 1] > 3){
                a[i + 1][j + 1] = max(a[i + 1][j + 1], max(a[i][j] + 1, a[i - 2][j - 2] + 3));
            }
        }
    }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX