資訊專欄INFORMATION COLUMN
摘要：給定整數(shù)序列的長(zhǎng)度和整數(shù)序列中依次的值，請(qǐng)你求出這個(gè)整數(shù)序列中最長(zhǎng)的單調(diào)減小的子序列的長(zhǎng)度以及不同但長(zhǎng)度都是最長(zhǎng)得單調(diào)減小的子序列的數(shù)量。輸入第行為一個(gè)整數(shù)，表示輸入的整數(shù)序列的長(zhǎng)度。對(duì)于問(wèn)題，聲明以第個(gè)元素為結(jié)尾的子序列的最長(zhǎng)的長(zhǎng)度。
題目：從一個(gè)由N個(gè)整數(shù)排列組成的整數(shù)序列中，自左向右不連續(xù)的選出一組整數(shù)，可以組成一個(gè)單調(diào)減小的子序列（如從{68 69 54 64 68 64 70 67 78 62 98 87}中我們可以選取出{69 68 64 62}這個(gè)子序列；當(dāng)然，這里還有很多其他符合條件的子序列）。給定整數(shù)序列的長(zhǎng)度和整數(shù)序列中依次的值，請(qǐng)你求出這個(gè)整數(shù)序列中“最長(zhǎng)的單調(diào)減小的子序列的長(zhǎng)度”以及“不同但長(zhǎng)度都是最長(zhǎng)得單調(diào)減小的子序列的數(shù)量”。
輸入第1行為一個(gè)整數(shù)N，表示輸入的整數(shù)序列的長(zhǎng)度（1≤N≤50000）。輸入第2行包括由空格分隔的N個(gè)整數(shù)（每個(gè)整數(shù)都在32位長(zhǎng)整型范圍內(nèi)）。
輸出包括一行，為兩個(gè)數(shù)字，分別為針對(duì)給定的整數(shù)序列求出的“最長(zhǎng)的單調(diào)減小的子序列的長(zhǎng)度”以及“值不同但長(zhǎng)度都是最長(zhǎng)得單調(diào)減小的子序列的數(shù)量”
樣例輸入
12
68 69 54 64 68 64 70 67 78 62 98 87
樣例輸出
4 2
對(duì)于這個(gè)題，一共有兩個(gè)小部分的問(wèn)題要解決。前一個(gè)問(wèn)題是最長(zhǎng)不上升子序列，屬于LIS問(wèn)題，使用動(dòng)態(tài)規(guī)劃解決，后一個(gè)問(wèn)題屬于去重問(wèn)題。
對(duì)于LIS問(wèn)題，聲明dp[i] 以第i個(gè)元素為結(jié)尾的子序列的最長(zhǎng)的長(zhǎng)度。
對(duì)第i個(gè)元素，與前i-1個(gè)元素進(jìn)行比較：
dp[i] = 1; //當(dāng)末尾只要一個(gè)元素時(shí) 長(zhǎng)度為1
如果 arr[i] < arr[j]:
如果dp[i] < dp[j] + 1 此時(shí)dp[i]的值會(huì)被更新為dp[j] + 1
其他情況不做處理
對(duì)于去重問(wèn)題：
“值不同但長(zhǎng)度都是最長(zhǎng)得單調(diào)減小的子序列的數(shù)量” 這里說(shuō)的是：
比如輸入：
6
2 1 2 1 2 1
輸出應(yīng)為 2 1
2 1 2 1 這兩個(gè)是值相同的，所以應(yīng)該當(dāng)做一個(gè)
使用size[i] 數(shù)組去記錄第i元素為結(jié)尾時(shí)，值不同但長(zhǎng)度都是最長(zhǎng)得單調(diào)減小的子序列的數(shù)量
每次在dp更新一遍以后，進(jìn)行size的更新。
去掉相同值的情況，如果只去關(guān)注最后結(jié)尾時(shí)：
因?yàn)槊看伪闅v都會(huì)更新?tīng)顟B(tài)，也就是說(shuō)如果有相同值的時(shí)候 后者會(huì)把前者的情況 都會(huì)過(guò)一遍，所以只要每次更新時(shí)保證只取相同值的最后一個(gè)出現(xiàn)的元素位置的size[j]即可，也就是最右邊的那個(gè)。
對(duì)于i元素所構(gòu)成的最長(zhǎng)子序列的前一個(gè)元素可能有很多不同值，所以要記錄這些值,并只取最右邊的。
最后size 和 dp都已經(jīng)生成了最終數(shù)組
然后對(duì)整個(gè)數(shù)組進(jìn)行遍歷， 找出最大序列 且值不同的序列的數(shù)量
方法同找單個(gè)i位置元素的值不同但長(zhǎng)度都是最長(zhǎng)得單調(diào)減小的子序列的數(shù)量 一致
其他說(shuō)明：
數(shù)據(jù)較大 使用java中的BigInteger
遍歷找值不同但長(zhǎng)度都是最長(zhǎng)得單調(diào)減小的子序列的數(shù)量時(shí) 使用倒序查找
代碼：
Scanner read = new Scanner(System.in);
int n = read.nextInt();
long[] arr = new long[n];
long[] dp = new long[n];
BigInteger[] size = new BigInteger[n];
for(int i = 0; i < n; ++i){
arr[i] = read.nextLong();
}
long max = 0;
for(int i = 0; i < n; ++i){
dp[i] = 1;
size[i] = new BigInteger("0");
for(int j = 0; j < i; ++j){
if(arr[j] > arr[i]){
if(dp[j] + 1 > dp[i]){
dp[i] = dp[j] + 1;
}
}
}
if(dp[i] > max){
//更新 最長(zhǎng)長(zhǎng)度
max = dp[i];
}
// 確定以arr[i]結(jié)尾的 子序列中 值不同但長(zhǎng)度都是最長(zhǎng)得單調(diào)減小的子序列的數(shù)量
if(dp[i] > 1){//如果 不是只有一個(gè)數(shù)字的時(shí)候
Set sl = new HashSet<>();
for(int j = i - 1; j >= 0; --j){
//從右向左查詢 只查詢第一次遇到的并且是最大長(zhǎng)度的 size[i]
// 沒(méi)有記錄路徑 通過(guò) arr[j] > arr[i] && dp[j] == dp[i] - 1 來(lái)確定是否是前一個(gè)轉(zhuǎn)移
// 遇到相同結(jié)尾的情況，更右邊的已經(jīng)包含了左邊的情況
if(arr[j] > arr[i] && dp[j] == dp[i] - 1 && !sl.contains(arr[j])){
sl.add(arr[j]);//去重
size[i] = size[i].add(size[j]);
}
}
}else{
//只有一個(gè)數(shù)字是 數(shù)量為1
size[i] = new BigInteger("1");
}
}
BigInteger maxBigI = new BigInteger("0");
Set set = new HashSet<>();
//遍歷整個(gè)序列 找出最大長(zhǎng)度 且值不同的序列的數(shù)量
for(int i = n - 1; i >= 0; --i){
if(dp[i] == max && !set.contains(arr[i])){
set.add(arr[i]);
maxBigI = maxBigI.add(size[i]);
}
}
System.out.println(max + " " + maxBigI.toString());
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/69324.html
摘要：可以調(diào)用方法將其轉(zhuǎn)換為一個(gè)對(duì)象是線程安全的，則沒(méi)有實(shí)現(xiàn)線程安全功能，所以性能略高。通過(guò)串聯(lián)更方便將該對(duì)象與的對(duì)象進(jìn)行比較。追加字符串插入替換刪除反轉(zhuǎn)輸出輸出改變的長(zhǎng)度，將只保留前面部分 String類是不可變類，即一旦一個(gè)String對(duì)象被創(chuàng)建以后，包括在這個(gè)對(duì)象中的字符序列是不可改變的，直至這個(gè)對(duì)象被銷毀 StringBuffer對(duì)象則代表一個(gè)字符序列可變的字符串，當(dāng)一個(gè)String...
摘要：序列化的這種過(guò)程，我們將其稱為腌制。而把模塊編譯成二進(jìn)制語(yǔ)言程序的這個(gè)過(guò)程叫做字節(jié)編譯，這個(gè)過(guò)程會(huì)產(chǎn)生一個(gè)與編譯的模塊對(duì)應(yīng)的文件。 常量： 在Python中常量的使用并不像java等其他編程語(yǔ)言一樣有特定的常量實(shí)現(xiàn)的關(guān)鍵字，在Python中定義需要用對(duì)象的方法來(lái)創(chuàng)建。 showImg(https://segmentfault.com/img/bVP6mZ?w=1232&h=703); ...
摘要：序列化的這種過(guò)程，我們將其稱為腌制。而把模塊編譯成二進(jìn)制語(yǔ)言程序的這個(gè)過(guò)程叫做字節(jié)編譯，這個(gè)過(guò)程會(huì)產(chǎn)生一個(gè)與編譯的模塊對(duì)應(yīng)的文件。 常量： 在Python中常量的使用并不像java等其他編程語(yǔ)言一樣有特定的常量實(shí)現(xiàn)的關(guān)鍵字，在Python中定義需要用對(duì)象的方法來(lái)創(chuàng)建。 showImg(https://segmentfault.com/img/bVP6mZ?w=1232&h=703); ...
摘要：知識(shí)點(diǎn)總結(jié)常用類字符類知識(shí)點(diǎn)總結(jié)常用類類型用來(lái)比奧斯在編碼中的字符。使用給定中的字符替換此序列的子字符串中的字符。將此字符序列用其反轉(zhuǎn)形式取代。返回最右邊出現(xiàn)的指定子字符串在此字符串中的索引。 Java知識(shí)點(diǎn)總結(jié)（常用類-字符類） @(Java知識(shí)點(diǎn)總結(jié))[Java, Java常用類] [toc] Char char類型用來(lái)比奧斯在Unicode編碼中的字符。Unicode用來(lái)處理各...
摘要：起因及介紹在早期的賬戶系統(tǒng)中，但凡有賬戶變動(dòng)，就會(huì)執(zhí)行一次數(shù)據(jù)庫(kù)操作。這時(shí)，在一次處理過(guò)程中，合并同一個(gè)賬戶的所有操作，最后只提交一次，就能帶來(lái)很大的優(yōu)化空間。根據(jù)業(yè)務(wù)需要，進(jìn)行增減轉(zhuǎn)賬凍結(jié)解凍操作。 起因及介紹 在早期的賬戶系統(tǒng)中，但凡有賬戶變動(dòng)，就會(huì)執(zhí)行一次數(shù)據(jù)庫(kù)操作。這樣在有復(fù)雜一些業(yè)務(wù)操作的時(shí)候，例如單筆交易涉及多個(gè)用戶多個(gè)費(fèi)用的資金劃撥，一個(gè)事務(wù)內(nèi)操作數(shù)據(jù)庫(kù)幾十次也就大量的存...
閱讀 1896·2021-09-24 09:48
閱讀 3236·2021-08-26 14:14
閱讀 1694·2021-08-20 09:36
閱讀 1484·2019-08-30 15:55
閱讀 3643·2019-08-26 17:15
閱讀 1441·2019-08-26 12:09
閱讀 618·2019-08-26 11:59
閱讀 3339·2019-08-26 11:57
