-> tối ưu bằng dp
dỏm, dp người ta xài có 2 vòng for kìa
done
Mệt mỏi với mấy thằng reverse dynamic programming vl
Đại khái nó cũng gần giống bài climbing stairs. Thay vì chọn bước 1 bước hay bước 2 bước thì mình chọn bước trái hay bước phải. Số điểm nó sẽ có lúc lặp lại
Lúc đầu tôi vẽ decision tree thì cũng kiểu chọn trái hay chọn phải. Chọn một hồi thì cứ max từng nhánh mà chọn -> lộn qua greedy -> sai -> xem solution -> ngộ ra
struct Solution {
int maximumScore(vector<int>& N, vector<int>& M) {
vector<int> arr(M.size() + 1);
for (int k = M.size(); k--;)
for (int i = 0; i <= k; ++i)
arr[i] = max(M[k] * N[i] + arr[i + 1], M[k] * end(N)[i - k - 1] + arr[i]);
return arr[0];
}
};Kiểu này chạy lại hên hên thì pass,REEEEEE
https://leetcode.com/submissions/detail/801682572/
Xem tệp đính kèm 1385964
pass hết nhưng nó đéo cho AC kì cục vậy
Chạy chậm quá chứ sao nữa.REEEEEE
https://leetcode.com/submissions/detail/801682572/
Xem tệp đính kèm 1385964
pass hết nhưng nó đéo cho AC kì cục vậy
có cái test thứ 135 https://leetcode.com/submissions/detail/801687063/ nó cho 5000 từ mỗi từ 300 ký tự luôn, chạy mất 1.1s ròi
Không cần Trie đâu bác. HashMap là đủ rồi.có cái test thứ 135 https://leetcode.com/submissions/detail/801687063/ nó cho 5000 từ mỗi từ 300 ký tự luôn, chạy mất 1.1s ròitoy phải chuyển qua string_view cho nó đỡ cấp phát động chỗ tách word thành prefix suffix pass hết mà nó lại chê lâu mới đao lòng
xem đáp án chúng nó viết cái trie mới qua
làm phát chăm phần chăm luôn
Submit test lấy thưởng đi bác.làm phát chăm phần chăm luônhttps://leetcode.com/submissions/detail/801715290/ 195ms lẹ hơn cái code 100% 290ms tận 1/3 thời gian
thằng lào viết test case chắc ko nghĩ tới cái minLen maxLen này àcó case nào mà cách này chậm ko
hack quá hack quá
------
holi shiet toy tìm ra được test case nó chạy tận 2.5s nàysubmit test case lấy coin thoy
nó là test case 135 hồi nãy 5000 chuỗi 300 ký tự nhưng có 1 chuỗi empty thành 4999 chuỗi 300 ký tự và 1 chuỗi empty. Làm vậy thì minLen=0 maxLen=300 chứ ko còn minLen=300 maxLen=300 mà "hack" chạy lẹ O(NWW) thành O(NW) nữa
Testcase này muốn nhanh thì đừng có loop từ min_len đến max_len nữa mà build 1 cái hash map, chứa len của các words. Rồi loop trong cái hash map đó thôi.làm phát chăm phần chăm luônhttps://leetcode.com/submissions/detail/801715290/ 195ms lẹ hơn cái code 100% 290ms tận 1/3 thời gian
thằng lào viết test case chắc ko nghĩ tới cái minLen maxLen này àcó case nào mà cách này chậm ko
hack quá hack quá
------
holi shiet toy tìm ra được test case nó chạy tận 2.5s nàysubmit test case lấy coin thoy
nó là test case 135 hồi nãy 5000 chuỗi 300 ký tự nhưng có 1 chuỗi empty thành 4999 chuỗi 300 ký tự và 1 chuỗi empty. Làm vậy thì minLen=0 maxLen=300 chứ ko còn minLen=300 maxLen=300 mà "hack" chạy lẹ O(NWW) thành O(NW) nữa
Testcase này muốn nhanh thì đừng có loop từ min_len đến max_len nữa mà build 1 cái hash map, chứa len của các words. Rồi loop trong cái hash map đó thôi.
Nếu testcase có đủ len từ 0 đến 300 thì vẫn phải loop hết thôi.
Ý tưởng thì đúng nhưng dùng TreeSet thì hợp lý hơn HashMap.Testcase này muốn nhanh thì đừng có loop từ min_len đến max_len nữa mà build 1 cái hash map, chứa len của các words. Rồi loop trong cái hash map đó thôi.
Nếu testcase có đủ len từ 0 đến 300 thì vẫn phải loop hết thôi.
submit test có thấy chả lời gì đâu chắc phải submit trên github à
thử 4700 words length 300 và 300 words len từ 0-299 của bác bribnt chưa
a = [...] # test case 135
import random
random_indices = random.sample(range(len(a)), min(300, len(a)))
word_len = 0
for i in random_indices:
a[i] = a[i][0:word_len]
word_len += 1
with open('336.txt', 'w') as f:
f.write('[')
f.write(f'"{a[0]}"')
for i in range(1, len(a)): f.write(f',"{a[i]}"')
f.write(']')Xác nhận là cái test case này làm TLE tất cả các cách nhé. Trie cũng chết nốt. Trie còn chậm hơn HashMap trừ khi Trie là nhiều ký tự trở lên ở mỗi level thì tui chưa thử.submit test có thấy chả lời gì đâu chắc phải submit trên github à
thử 4700 words length 300 và 300 words len từ 0-299 của bác bribnt chưacũng vậy thoy hack quá
ví dụ toy generate từ test case 135 nè:
