Problem 1 (最長遞增子序列 21%)
考慮一個數列在刪除最少個數的情況下，使得剩下的數字呈現遞增狀態。例如，有一個數列為8,20,27,17,13,28,35,31，若保留前三個數字，其餘的全部刪除，剩下的就是一個遞增序列；或者是保留第一、第三、第六及第七，其餘的全部刪除，剩下的也是一個遞增序列，但是與前一個例子相比，其遞增的序列較長。
輸入說明：輸入之奇數列為下一行數列中的個數，偶數列為數列資料，代表一組測試資料。每個數字與數字間的區隔為一個空白符號，當奇數列為0時表示結束。(請參照輸入範例)
輸入範圍：每個數列最少有2個數字，最多不超過100個。每個數列中的數字皆大於0，小於1000，且不重覆。
輸入範例：test1.txt
8
8 20 27 17 13 28 35 31
15
13 14 55 21 66 72 23 73 1 2 88 83 84 24 7
0
輸出說明：每組測試的數列皆要輸出欲刪除的個數。(請參照輸出範例)
輸出範例：result1.txt
3
7
Dim s, m, n, Ans, Fa, Min, t
回覆刪除Private Sub Form_Load()
Me.Hide
Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
Do While Not EOF(1)
Input #1, t
If t <> 0 Then
Line Input #1, m
Fa = Split("O X")
Min = -1
Call A1(0, "")
Print #2, Min
End If
Loop
Close
Close
End
End Sub
Sub A1(a, b)
If a = t Then
Call A2(b)
Else
For i = 0 To 1
Call A1(a + 1, Fa(i) & " " & b)
Next
End If
End Sub
Sub A2(a)
Dim Mi, Mt As Boolean, Ti
Ti = 0
k = Split(a)
s = Split(m)
For i = 0 To UBound(s)
If k(i) = "X" Then s(i) = "X": Ti = Ti + 1
Next
Mt = True
Mi = -1
For i = 0 To UBound(s)
If Mi = -1 And s(i) <> "X" Then Mi = s(i)
If s(i) <> "X" And Val(Mi) < Val(s(i)) Then Mi = s(i)
If s(i) <> "X" And Val(Mi) > Val(s(i)) Then Mt = False
Next
If Min = -1 And Mt = True Then Min = Ti:
If Min > Ti And Mt = True Then Min = Ti
End Sub
Dim X()
回覆刪除Private Sub Form_Load()
Me.Hide
Open App.Path & "\in.txt" For Input As #1
Open App.Path & "\out.txt" For Output As #2
Do While Not EOF(1)
Input #1, N
If N = 0 Then Exit Do
ReDim X(N)
ans = 0
For i = 1 To N
Input #1, X(i)
Next i
Max = 0
Do
p = False
For i = 1 To N
If Max = 0 Then Max = Combo(i)
If Max < Combo(i) Then X(i) = 0
Next i
Loop Until p = False
Print #2, Max
Loop
Close #2
Close #1
End
End Sub
Function Combo(A) As Integer
ans = 0
M = 0
For i = 1 To (UBound(X) - 1)
If X(i) < X(i + 1) And i <> A And i + 1 <> A And X(i) <> 0 And X(i + 1) <> 0 Then ans = ans + 1
Next i
Combo = ans
End Function