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 
12

Test 1

Input 
3 2
1 2 3
4 2 3
Output 
17

Bình luận


  • -1
    HoaBanMaTuy    3:31 p.m. 28 Tháng 11, 2023 ← đã chỉnh sửa 

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


    • 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