题目: count PAT's输入一串字符，其中字符集为 {P,A,T}， 求解字符中包含多少个PAT子序列。例如：PATT 包含2个PAT 子序列， PAATT包含4个PAT子序列。 问题分析： 对于字符串s[n]， 考虑某位置s[i]，相对于s[i-1]增加了s[i]，考虑增加s[i]对PAT子序列的影响：如果s[i]是T字符，那么当前的PAT子序列增加的数目，就是当前PA子序列的数目，因为前面有多少个PA，增加一个T，就会增加多少个PAT；同理，如果s[i]是A字符，那么当前的PA 的增加数目，就是当前的P的字符数目。 复杂度分析 只需要简单的遍历一遍s[n]，复杂度为O(n) 通过代码...

​看到这题，很容易观察到这是一个包含子问题的，直接dp。 题目要求是不相邻的子序列值。 什么样子会帮助满足最大呢？1，序列包含尽可能多的数2，序列包含尽可能大的数。考虑不相邻的话，要不要加入第i个数，需要考虑的问题是它前一个i-1 要不要加入，至于i-2则不需要考虑，因为加入第i个数必然可以加入不相邻的i-2 。换句话说，你不会跳过3个数。换成代码就是 dp[i+3] = max(dp[i+2], dp[i+1]+arr[i]) class Solution { public: long long subsequence(int n, vector<int>& ...

NC142 最长重复子串 题目描述 一个重复字符串是由两个相同的字符串首尾拼接而成，例如abcabc便是长度为6的一个重复字符串，而abcba则不存在重复字符串。给定一个字符串，请编写一个函数，返回其最长的重复字符子串。若不存在任何重复字符子串，则返回0。 想法 没想到什么特别的解法，直接暴力= = 题目中说是重复子串，其实规定了是重复一次的，多次的不算，所以暴力就o(N^3), 勉强接受了。 bool judge(string& a,int s,int len) { for(int i=s;i<s+len;i++) { ...