f941 - Coder King
題目描述
題目描述了一個關於 Gino、Arik 和他們能力的奇幻故事。Arik 擁有將人變成數字的能力，而 Gino 則擁有 "Heaviest" 的能力。最終，Gino 被 Arik 變成了一串數字，而 Gayry 需要找到這串數字中最長非嚴格遞增子序列 (LIS) 的長度，才能救出 Gino。
解題思路
題目要求計算一串數字序列的最長非嚴格遞增子序列的長度。可以使用動態規劃或貪心算法來解決這個問題。由於題目限制了數字的範圍 (1, 2, 3)，可以使用貪心算法優化動態規劃的空間複雜度。
具體來說，可以維護一個數組 tails，其中 tails[i] 表示所有長度為 i+1 的非嚴格遞增子序列的最小末尾元素。遍歷輸入序列，對於每個數字 num，如果 num 大於 tails 中所有元素，則將 num 添加到 tails 的末尾。否則，在 tails 中找到第一個大於等於 num 的元素，並將其替換為 num。最終，tails 的長度就是 LIS 的長度。
複雜度分析
- 時間複雜度: O(n log n) (二分查找)
- 空間複雜度: O(n)
程式碼
#include <stdio.h>
using namespace std;
int a[3];
char c;
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
while(1){
c=getchar_unlocked();
if(c=='1'){
++a[0];
if(a[1])--a[1];
else if(a[2])--a[2];
}
else if(c=='2'){
++a[1];
if(a[2])--a[2];
}
else if(c=='3'){
++a[2];
}
else{
break;
}
}
write(a[0]+a[1]+a[2]);
}