Xâu min
Xem PDF
Điểm:
1300 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho xâu \(S\) chứa các kí tự \(1 \ldots 9\) (\(|S| \leq 1000\) kí tự) và số nguyên \(K\) (\(1 \leq K \leq |S|\)). (\(|S|\) độ dài của xâu \(S\))
Yêu cầu: Chọn \(K\) kí tự trong xâu \(S\) theo thứ tự ban đầu để tạo thành số \(X\) gồm \(K\) chữ số có giá trị bé nhất.
Input
- Dòng 1: Ghi số \(K\).
- Dòng 2: Ghi xâu \(S\).
Output
- Ghi một số duy nhất \(X\).
Example
Test 1
Input
3
89678982 Output
672
Bình luận
ý tưởng dành cho bạn nào thích dp :
suy ra ta có công thức dp như sau :
TH 1 : chọn số thứ i + 1 : dp[i + 1][j + 1] = min(____,dp[i][j] + s[i + 1]) , điều kiện : j + 1 <= k
TH 2 : không chọn số thứ i + 1 : dp[i + 1][j] = min(____,dp[i][j])
code mẫu cho bạn nào còn : https://ideone.com/CIbbBz
10 bình luận nữa