wordpress网站设密码错误,dw网站建设步骤,做家教网站赚钱么,阳江网红服务区【问题描述】 小蓝特别喜欢单调递增的事物。 在一个字符串中#xff0c;如果取出若干个字符#xff0c;将这些字符按照在字符串中的顺 序排列后是单调递增的#xff0c;则成为这个字符串中的一个单调递增子序列。 例如#xff0c;在字符串 lanqiao 中#xff0c;如果取出字…【问题描述】 小蓝特别喜欢单调递增的事物。 在一个字符串中如果取出若干个字符将这些字符按照在字符串中的顺 序排列后是单调递增的则成为这个字符串中的一个单调递增子序列。 例如在字符串 lanqiao 中如果取出字符 n 和 q则 nq 组成一个单 调递增子序列。类似的单调递增子序列还有 lnq、i、ano 等等。 小蓝发现有些子序列虽然位置不同但是字符序列是一样的例如取第 二个字符和最后一个字符可以取到 ao取最后两个字符也可以取到 ao。小蓝 认为他们并没有本质不同。 对于一个字符串小蓝想知道本质不同的递增子序列有多少个 例如对于字符串 lanqiao本质不同的递增子序列有 21 个。它们分别是
l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、
anq、lno、ano、aio。
请问对于以下字符串:
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
本质不同的递增子序列有多少个
解题思路: 1.动态规划建立dp数组,dp[i]表示以num[i]为结尾的子序列个数 满足添加的num[i] 我们动态规划的转移条件就2个。 一个是满足题目要求的时候一个是相等时当题目字母相等时前面的字母已经累加过一次的所以我们要把前累计过的去掉和去重一样的关系。 A:假如num[j]是小于num[i]的, 那么dp[i]dp[i]dp[j]就是我们要求的答案。 B:假如numj是等于num[i]的 dp[i]dp[i]-dp[j] 因为每一个字母都算一个序列所以dp初始化为1
代码如下:
#include iostream
#include cstring
using namespace std;
const int N 200;
typedef long long LL;
int dp[N];
string str tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl;int main() {for (int i 0; i N; i)dp[i] 1;for (int i 1; i N; i)for (int j 0; j i; j) {if (str[i] str[j])dp[i] dp[j];else if (str[i] str[j])dp[i] - dp[j];}LL ans 0;for (int i 0; i N; i)ans dp[i];cout ans endl;return 0;
}
