第十一届蓝桥杯（决赛）之本质上升序列

解析：

先把题目中的字符串给出来：tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

一、分析

• 是一个计数问题，不是最优化问题

• 直接暴力求解：例如遍历字符串，新建list，每次都把当前字符c加入list，并把list现存的字符串最后一位小于c的字符串加上c加入list中，然后排序判断。但是时间复杂度：(1+100)*100/2+((1+100)*100/2)^2 ==>O(n^2)+O(n4)，证明不可行

• 计数问题==>记忆化搜索，dp

如果dp[i]表示以str[i]为尾的字符串的个数
str[j] str[i]==str[j],str[i]=str[i]-str[j]
str[i]

之前有一个问题没想通：比如遇到"abcab"时，第一个b有一个ab，第二个b有2个ab，后来才发现dp[第二个a]=0，所以就没问题了。

• 填充数组

import java.util.Arrays;
Arrays.fill(dp,1);

二、代码

import java.util.Arrays;public class ExaminationD {public static void main(String[] args) {int n = 200;int[] dp = new int[n];char[] charArray= new String("tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjr" +"prrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjai" +"htniptwoulxbaeqkqhfwl").toCharArray();
//        char[] charArray = new String("abcab").toCharArray();Arrays.fill(dp,1);for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {if (charArray[i]>charArray[j]) dp[i]+=dp[j];if (charArray[i]==charArray[j]) dp[i]=0;}}long res = 0l;for (int i = 0; i < n; i++) {//System.out.println(String.format("dp[%d]=%d",i,dp[i]));res+=dp[i];}System.out.println(res);}
}