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

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Tác giả:

Small

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

-1

#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>>

2 phản hồi

1

161007thanhhiu 4:35 p.m. 29 Tháng 10, 2023

nhìn dp - alien rén v :))

1 phản hồi

0

rukashii 4:04 p.m. 19 Tháng 12, 2021

hóng người if 5 trường hợp k

6

SPyofgame 9:01 a.m. 3 Tháng 5, 2021

bài này tăng \(k \rightarrow n\) vẫn solvable : ))