K hẳn trick lỏ đâu. Não to lắm đấy. Cái dp là giống kiểu set để lưu tổng những giá trị hiện tại của rewards được pick.có vẻ trick lỏ rồi
dp & ((1 << v) - 1) đoạn này là nó đang ignore những rewards lớn hơn hoặc bằng value của reward hiện tại.dp |= x << v đoạn này là nó cộng reward hiện tại vòa toàn bộ những reward nhỏ hơn và add vào set.
Cám ơn thím vì giải thích làm code dễ hiểu hẳn.
import java.math.BigInteger;
class Solution {
public int maxTotalReward(int[] rs) {
Arrays.sort(rs);
int n = rs.length;
BigInteger dp = BigInteger.ONE;
int currValue = -1;
for (int r: rs) {
if (r == currValue) {
continue;
}
currValue = r;
BigInteger maskBitsLessThanCurr = BigInteger.ONE.shiftLeft(r).subtract(BigInteger.ONE);
BigInteger infoBitsLessThanCurr = dp.and(maskBitsLessThanCurr);
dp = dp.or(infoBitsLessThanCurr.shiftLeft(r));
}
return dp.bitLength() - 1;
}
}
Thường leetcode nó accept solution O 10^8 mà, nên O n^2/32 với 5*10^4 sẽ vẫn pass.Cuối cùng câu 4 vẫn là O(n^2) chứ không thể nhỏ hơn đc. Dùng trick lỏ bitset thì giảm xuống O(n^2/32) thôi chứ có xuống O(nlog) hay O(n) đâu. Nhìn constraint là 5*10^4 thì mình cứ mặc định phải tối ưu dưới cả O(n^2). Thôi rút kinh nghiệm lần sau ko nghĩ đc thì làm tối ưu O(n^2). Chứ bài này mình đánh giá ko hay
fence nạp card rồi àcó khóa dp với dp advance(premium) đó bác tổng cộng 100 câu
mới giải dc 12 câu
Xin ít rating lên 2k cái nha fencehôm nay sẽ là ngày em gỡ lại rating sau mấy contest tan nát
dân CP mấy bài này nó gặp như cơm bữa. quen dạng + template code nhanh lắm
Toy cũng thế, thủ sẵn template dễ ăn hẳn. Xử lí edge case hơi sida thôi ăn 3 bug Q4 cmnr1 bug, may thủ sẵn template segment tree
Bài 3 lúc đầu quên xử lí tí frequency chứ ý tưởng thì khá oke
Giải bằng nlogn là ngon ko cần O(n)
