Editorial for Cắt số

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Ta có thể giải bài toán này với các thông tin mấu chốt sau:

Vì lúc nào ta phải lấy chính xác ~3~ phần tử trong dãy, ta nên lấy nhiều nhất số lượng phần tử có thể, và chỉ để lại trong dãy ~(n \bmod 3)~ phần tử.
Thay vì nghĩ đến việc cực đại hóa tổng các số có thể lấy được, ta có thể nghĩ đến việc tối thiểu hóa số lượng phần tử để lại trong dãy.

Vì số lượng phần tử để lại nhỏ (không quá 2 phần tử), ta có thể duyệt toàn bộ các phần tử để lại và tìm tổng nhỏ nhất của chúng.

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
long long A[MAXN];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        long long sum=0,ans=1e18;
        for(int i=1;i<=n;i++)
        {
            cin>>A[i];
            sum+=A[i];
        }
        if(n%3==0) ans=0;
        if(n%3==1) for(int i=1;i<=n;i+=3) ans=min(ans,A[i]);
        if(n%3==2) for(int i=1;i<=n;i+=3) for(int j=i+1;j<=n;j+=3) ans=min(ans,A[i]+A[j]);
        cout<<sum-ans<<"\n";
    }
}

Comments

Please read the guidelines before commenting.

bemittom commented on May 31, 2026, 3:28 a.m.

Bài này dùng DP trong O(N) cũng được

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    if n < 3: print(0)
    else:
        dp = [0, 0, 0]
        for i in range(3, n + 1):
            dp.append(max(dp[i - 1], dp[i - 3] + a[i - 3] + a[i - 2] + a[i - 1]))
        print(dp[n])

t = int(input())
while t:
    t -= 1
    solve()