蓝桥杯 本质上升序列

题目描述:

小蓝特别喜欢单调递增的事物。 在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。 例如，在字符串 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。 请问对于以下字符串（共 200
个小写英文字母，分四行显示）：（如果你把 以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在 试题目录下有一个文件inc.txt，内容与下面的文本相同）
本质不同的递增子序列有多少个？

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

解题思路:

拿到题目一看是字母比较大小，直接想到遍历字符串比较就行

1：先创建一个数组a[]=new int [字符串的具体长度]，它的数值是统计以每一个字符结尾的子字符串的个数的，比如“12”，a[0]的值代表以1结尾的子字符串=1，a[1]以2结尾有 “2”，“12”，所以a[1]=2;

2：因为每个字符都是字符串的子序列，可以令a[i]=1；

3:不难理解，a[i]的值又全体a[j]共同决定(0<j<i)

比如说有一个字符串有数字构成（和字符一样）：127837；

按照a的定义 7 17 27 127属于a[5]，因为他们的结尾都是7且都是上升序列，但是累加时这四个和a[2]对应的序列集重复 因此需要在a[5]-a[2]

代码:

String s="tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
	
		int a[]=new int[200];
		int count=0;
		for(int i=0;i<200;i++) {
			a[i]=1;
		}
		for(int i=1;i<200;i++) {
			for(int j=0;j<i;j++) {
				if(s.charAt(i)>s.charAt(j)) {
					a[i]+=a[j];
				}
				else if(s.charAt(i)==s.charAt(j)) {
					a[i]-=a[j];
				}
			}
		}
		for(int i=0;i<200;i++) {
			count+=a[i];
		}
		System.out.println(count);