Làm bài thi - LCOJ: Luyện Code Online Judge

DOEXAM - Làm bài thi

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Tí rất yêu thích và học giỏi môn Tin học, vì vậy năm nay Tí đã đăng ký tham dự kỳ thi HSG lớp ~10~ do nhà trường tổ chức. Vào buổi thi, sau khi nhận được đề Tí thấy đề thi có ~n~ bài, bài thứ ~i~ có số điểm là ~d_i~. Sau khi phân tích kỹ các bài Tí thấy với khả năng của mình thì thời gian để làm mỗi bài là như nhau và mình chỉ đủ thời gian làm ~k~ bài. Tuy nhiên quy định của BTC lại không cho phép thí sinh bỏ qua hai bài liên tiếp (nếu thí sinh bỏ qua bài thứ ~i~ và bài thứ ~i + 1~ thì tất cả các bài từ bài thứ ~i~ trở đi đều không được tính điểm). Tất nhiên với trí thông minh của mình thì Tí có thể lựa chọn các bài để làm sao cho đạt được số điểm tối đa. Em hãy tính xem, số điểm tối đa Tí có thể đạt là bao nhiêu?

Input

Dòng đầu chứa hai số nguyên dương ~n~ và ~k~;
Dòng thứ hai chứa ~n~ số nguyên dương ~d_1, d_2, …, d_n~.

Giới hạn:

~1 ≤ n, k ≤ 25; 1 ≤ d_1, d_2, …, d_n ≤ 1000~.

Output

Một số nguyên duy nhất là số điểm tối đa Tí có thể đạt được.

Sample

Input #1

5 2
7 3 3 9 10

Output #1

Hint

Xét #1: Tí chọn làm các bài số ~2~ và số ~4~, số điểm đạt được là ~3 + 9 = 12~.

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

include <iostream>

using namespace std;

int a[25];
int MAXS = 0;
int sum = 0;

int max(int x, int y) {
    return x > y ? x : y;
}

void Try(int i, int dem, int n, int k) {
    if (dem == k) {
        MAXS = max(MAXS, sum);
        return;
    }
    for (int j = i + 1; j <= i + 2; j++) {
        if (j < n) {
            sum += a[j];
            Try(j, dem + 1, n, k);
            sum -= a[j];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sum = a[0];
    Try(0, 1, n, k);

    sum = a[1];
    Try(1, 1, n, k);

    cout << MAXS;
    return 0;
}

quay lui nhé các bạn.

0

long123 đã bình luận lúc 26, Tháng 1, 2026, 3:38

tai sao nguoi ta ko lay 3 va 10 v mn

include <bits/stdc++.h>

using namespace std;

int main() { ios::syncwithstdio(false); cin.tie(nullptr);

int n, k;
cin >> n >> k;
vector<int> d(n + 1);
for(int i = 1; i <= n; i++) cin >> d[i];

const int NEG_INF = -1e9;
// dp[i][j][t]: xét tới bài i, đã làm j bài, trạng thái t
// t = 0: bài trước không bỏ
// t = 1: bài trước bỏ 1
// t = 2: đã bỏ hai liên tiếp, không cộng điểm nữa
int dp[26][26][3];
for(int i = 0; i <= n; i++)
    for(int j = 0; j <= k; j++)
        for(int t = 0; t <= 2; t++)
            dp[i][j][t] = NEG_INF;

dp[0][0][0] = 0; // trước bài đầu tiên, chưa làm, chưa bỏ

for(int i = 1; i <= n; i++){
    for(int j = 0; j <= k; j++){
        for(int t = 0; t <= 2; t++){
            int cur = dp[i-1][j][t];
            if(cur < NEG_INF/2) continue;

            // 1. Chọn làm bài i
            if(t != 2 && j + 1 <= k){
                dp[i][j+1][0] = max(dp[i][j+1][0], cur + d[i]);
            }
            if(t == 2){
                // đã bỏ 2 liên tiếp, bài sau không cộng điểm
                dp[i][j][2] = max(dp[i][j][2], cur);
            }

            // 2. Chọn bỏ bài i
            if(t == 0){
                dp[i][j][1] = max(dp[i][j][1], cur);
            }
            if(t == 1){
                dp[i][j][2] = max(dp[i][j][2], cur); // bỏ 2 liên tiếp → khóa
            }
        }
    }
}

int ans = 0;
for(int j = 0; j <= k; j++)
    for(int t = 0; t <= 2; t++)
        ans = max(ans, dp[n][j][t]);

cout << ans << "\n";
return 0;

}

-2

anhthu240712 đã bình luận lúc 24, Tháng 11, 2025, 15:58

ai đến sau thì bày mìnhh quy hoạch độn với ạ

-1

MANHOOH đã bình luận lúc 22, Tháng 8, 2025, 12:20

ủa mn ơi output 2 cho mảng 7 3 3 9 10 đáng lẽ phải ra 19 chứ 10 + 9 lơn nhất liên tiếp mà sao 12 ạ

0

TangNguyen123 đã bình luận lúc 18, Tháng 9, 2025, 8:36

Theo đề bài thì ta biết được rằng bạn Tí không được phép bỏ qua 2 bài liên tiếp. Tức là ban đầu tí được phép làm bài 1, bỏ bài 2 và làm bài 3. Hoặc bỏ bài 1, làm bài 2 va tiếp như thế chứ không được phép bỏ qua bài 1 và bài 2 để làm bài 3.