ps:枚举翻转区间的端点的数值,因为每个数都在0~9范围内,所以只需要枚举45种情况(C(10,2)组合数)。b串:0 1 2 3 4 5 6 7 8 9,枚举翻转区间的端点的数值3,6,得到新的b串:0 1 2 3 6 5 4 3 6 7 8 9,让这个串与原串跑一遍普通的最长公共子序列就能得到答案。注意保留一份端点值。怎么更新翻转区间的位置我还没搞明白~
int solve() { dp[0][0] = 0; for (int i = 1; i <= n; ++i) dp[i][0] = 0; for (int i = 1; i <= m; ++i) dp[0][i] = 0;
for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { //dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + (a[i] == b[j]); dp[i][j] = dp[i - 1][j]; l[i][j] = l[i - 1][j]; r[i][j] = r[i - 1][j]; if (a[i] == b[j]) { dp[i][j]++; if (j == L && l[i][j] == 0) l[i][j] = i; if (j == R) r[i][j] = i; } if (dp[i][j] < dp[i][j - 1]) { dp[i][j] = dp[i][j - 1]; l[i][j] = l[i][j - 1]; r[i][j] = r[i][j - 1]; } } } return dp[n][m]; }