博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Hills And Valleys
阅读量:5143 次
发布时间:2019-06-13

本文共 770 字,大约阅读时间需要 2 分钟。

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];
}

 

转载于:https://www.cnblogs.com/zgglj-com/p/9454379.html

你可能感兴趣的文章
nativeXml使用方法
查看>>
LightOJ1074Extended Traffic(bellman_ford最短路+负环标记)
查看>>
Android Studio 编译不通过,报错“找不到org.apache.http
查看>>
springmvc集成Freemarke配置的几点
查看>>
Django 学习
查看>>
Linux-以指定用户运行redis
查看>>
Linux-socket的close和shutdown区别及应用场景
查看>>
xpath
查看>>
parted分区
查看>>
图片标签img
查看>>
JavaScript语言中文参考手册.chm
查看>>
表哥的Access入门++以Excel视角快速学习数据库知识pdf
查看>>
TC 配置插件
查看>>
关于异步reset
查看>>
索引优先队列的工作原理与简易实现
查看>>
并发编程简介
查看>>
基于K-近邻分类算法的手写识别系统
查看>>
使用easyui的form提交表单,在IE下出现类似附件下载时提示是否保存的现象
查看>>
PC站跳转M站的方法
查看>>
wow 各职业体验(pvp)
查看>>