Bài 1 ​

Giả sử dãy có phần tử bằng $0$. Ta luôn chọn nó đầu tiên vì luôn khiến đáp án tốt hơn. Nếu dãy có phần tử min là $x$, phần tử này sẽ đóng góp vào đáp án $a[x]\ast (n-2)$. Ta coi như là giảm dãy đi $a_x$ đơn vị, lúc này xuất hiện thêm các phần tử $0$, ta chỉ việc xoá chúng đi và làm lại bước trên.

Đáp án cũng được cộng với $min(a[x-1],a[x+1])-a[x]$ (không xoá luôn mà có thể để sau này mới xoá $x$, chú ý: ta coi là dãy đang giảm đi $a[x]$ đơn vị).

Tóm tắt các bước:

• Tìm phần tử nhỏ nhất là $x$.
• Cộng vào đáp án cuối cùng $a[x]\ast (n-2)$ với $n$ là số giá trị còn lại.
• Cộng vào đáp án cuối cùng $min(a[x-1],a[x+1])-a[x]$.
• Giảm cả dãy đi $a[x]$, xoá các phần tử $0$.

Có thể cài đặt bằng Segment tree, không cần phải thực hiện thao tác xoá mà chỉ cần giảm trên Segtree.

Bài 2 ​

Đáp án luôn $\le 7$ vì một số chỉ có tối đa $6$ ước nguyên tố khác nhau. Ta tính mảng $dp(i,j)$ là số cách chọn $j$ phần tử sao cho có $gcd=i$.

Gọi số lượng số chia hết cho $j$ là $k$. Số cách chọn $i$ phần tử từ $k$ phần tử là $C_i^k$. Sau khi khởi tạo $dp(i,j)=C_k^i$, ta chỉ cần trừ hết đi $dp(i\times 2,j)$, $dp(i\times 3,j)$, ...

Bài 3 ​

Ta chặt nhị phân đáp án, giả sử xét giá trị $x$, ta cần xem có tồn tại cách chọn sao cho số lượng phần tử $\le x$ có $\ge k$ hay không. Ta sẽ coi những phần tử $a_i\le x$ là $a_i=1$, những phần tử $a_i>x$ là $a_i=0$. Ta nghĩ đến $dp$ để chọn được tổng $\ge k$.

Gọi $dp(i,j)$ là tổng nếu đã xét $i$ phần tử đầu và đã chọn tối đa $j$ đoạn. Công thức:

$dp(i,j)=max(dp(i-1,j),dp(i,j-1))$.

Nếu trong các phần tử $1$, $2$, ..., $i+1$, ta có đoạn $[L,R]$ với $R$ lớn nhất thì ta sẽ ưu tiên chọn đoạn $[L,R]$ này để mở rộng ra nhiều nhất, tổng được mở rộng ra đúng bằng $a_j$ với $j$ từ $i+1$ đến $R$. Do đó $dp(nxt(i),j+1)=max(dp(i,j)+sum(nxt(i))-sum(i))$ với $nxt(i)$ là $R$ lớn nhất sao cho $L\le i+1$ và $sum$ là mảng tổng tiền tố.

Cách làm trên là đúng vì mỗi lần ta chỉ thêm các phần tử chưa được xét, dù một phần tử bị nhiều đoạn đè lên.