题解 | #密码截取#

密码截取

https://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    string s;
    int res = 1;
    cin >> s;
    int n = s.size();
    // 代表以下标为n结尾的码串的最长有效密码传长度
    vector<vector<int>> dp(n, vector<int>(2, 1));
    // [i][0]代表有效密码串不完全相同的情况,[i][1]代表有效密码串完全相同的情况


    for (int i = 1; i < n; i++) {
        if (s[i] == s[i - 1]) {
            dp[i][1] = dp[i - 1][1] + 1;
            res = max(res, dp[i][1]);
        } else {
            int tmp1 = 1, tmp2 = 1;
            if (i - 1 - dp[i - 1][1] >= 0 && s[i] == s[i - 1 - dp[i - 1][1]]) {
                tmp1 = dp[i - 1][1] + 2;
            }
            if (i - 1 - dp[i - 1][0] >= 0 && s[i] == s[i - 1 - dp[i - 1][0]]) {
                tmp2 = dp[i - 1][0] + 2;
            }
            dp[i][0] = max(tmp1,tmp2);
            res = max(res, dp[i][0]);
        }
    }
    cout << res << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

动态规划的核心是定义过程量 以及 考虑过程量之间的关系。

本题对于对称 分成了全部相同和 非全部相同两种情况进行考虑, 并考虑了他们之间的关系。

全部评论

相关推荐

昨天 10:56
门头沟学院 Java
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务