Trò chơi trên dãy số (DHHV 2021)

Tác giả:

Dạng bài

Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Được mẹ giao nhiệm vụ ra các bài tập về phép cộng và phép nhân cho em Phúc, chị Hồng đã nghĩ ra một trò chơi trên dãy số để em Phúc không chỉ rèn luyện tính toán mà còn rèn luyện tư duy như sau: Cho một số nguyên dương \(k\) cùng với hai dãy số nguyên \(a_1,a_2,…,a_n\) và \(b_1,b_2,…,b_n\), em Phúc cần chọn \(k\) chỉ số \(1≤ i_1<i_2<⋯<i_k≤ n\) trên dãy thứ nhất và \(k\) chỉ số \(1≤ j_1<j_2<⋯<j_k≤ n\) trên dãy thứ hai sao cho \(S=a_{i_1}× b_{j_1}+a_{i_2}× b_{j_2}+⋯+a_{i_k}× b_{j_k}\) đạt giá trị lớn nhất. Để kiểm tra kết quả của em Phúc, Hồng nhờ bạn lập trình giải bài toán trên.

Yêu cầu: Cho số nguyên dương \(k\) và hai dãy số nguyên, hãy tìm \(k\) chỉ số trên dãy thứ nhất và \(k\) chỉ số trên dãy thứ hai để giá trị \(S\) đạt giá trị lớn nhất.

Input

Dòng đầu chứa hai số nguyên dương \(n,k\).
Dòng thứ hai chứa \(n\) số nguyên mô tả dãy số nguyên \(a_1,a_2,…,a_n\).
Dòng thứ ba chứa \(n\) số nguyên mô tả dãy số nguyên \(b_1,b_2,…,b_n\).

Output

Ghi ra một dòng chứa một số nguyên \(S\) lớn nhất cần tìm.

Constraints

\(k\leq n\leq 1000,k\leq 5\)
\(|a_i|\leq 10^6\) với mọi \(1\leq i\leq n\)
\(|b_j|\leq 10^6\) với mọi \(1\leq j\leq n\)

Scoring

Subtask \(1\) (\(25\%\) số điểm): \(k=1\)
Subtask \(2\) (\(25\%\) số điểm): \(k=2\)
Subtask \(3\) (\(25\%\) số điểm): \(k=3\)
Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm

Example

Test 1

Input

3 1
1 2 3
4 2 3

Output

Test 1

Input

3 2
1 2 3
4 2 3

Output

Bình luận

#include <bits/stdc++.h>
using namespace std;
long long n,dp[1005][1005][7],k,a[1005],b[1005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
//    freopen("kseqgame.inp","r",stdin);
//    freopen("kseqgame.out","w",stdout);
    cin>>n>>k;
    for(long long i=1;i<=n;i++)
        cin>>a[i];
    for(long long i=1;i<=n;i++)
        cin>>b[i];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            for(int q=1;q<=k;q++)
                dp[i][j][q]=-1e18;
    for(long long i=1;i<=n;i++)
        for(long long j=1;j<=n;j++)
            for(long long q=1;q<=k;q++)
            {
                dp[i][j][q]=max(dp[i-1][j][q],dp[i][j-1][q]);
                dp[i][j][q]=max(dp[i][j][q],dp[i-1][j-1][q-1]+a[i]*b[j]);
            }
    cout<<dp[n][n][k];
    return 0;
}

khử đệ quy này mấy nhóc !!
<<Bài dễ vãi lozz>>

1

PY2GTranNguyenAnhKhoi 9:56 p.m. 8 Tháng 12, 2023

nhìn tên là choáy rùi :)) cho vô hội ae của Huấn làm ăn là phát tài liền:)

0

HoaBanMaTuy 12:32 p.m. 18 Tháng 12, 2023

kkk ko dám

1

Mochiracvc1 8:33 a.m. 29 Tháng 11, 2023

ui liều vậy man =)

0

HoaBanMaTuy 12:32 p.m. 18 Tháng 12, 2023

ủa gửi code bị ban à bro

0

Mochiracvc1 5:29 p.m. 18 Tháng 12, 2023

Hình như là bị khóa chat =)

3 bình luận nữa