第十一届蓝桥杯（决赛）之本质上升序列
第十一届蓝桥杯（决赛）之本质上升序列
解析：
先把题目中的字符串给出来：tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
一、分析
-
是一个计数问题，不是最优化问题
-
直接暴力求解：例如遍历字符串，新建list，每次都把当前字符c加入list，并把list现存的字符串最后一位小于c的字符串加上c加入list中，然后排序判断。但是时间复杂度：(1+100)*100/2+((1+100)*100/2)^2 ==>O(n2)+O(n4)，证明不可行
-
计数问题==>记忆化搜索，dp
如果dp[i]表示以str[i]为尾的字符串的个数 之前有一个问题没想通：比如遇到"abcab"时，第一个b有一个ab，第二个b有2个ab，后来才发现dp[第二个a]=0，所以就没问题了。
str[j]
str[i]
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);}
}