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

View as PDF

Points: 1800 (p) Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

Đượ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\)\(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

Comments


  • 0
    HoaBanMaTuy    3:31 p.m. 28 nov, 2023 edited

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

    • 1
      161007thanhhiu    4:35 p.m. 29 oct, 2023

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


      • 0
        rukashii    4:04 p.m. 19 dec, 2021

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


        • 6
          SPyofgame    9:01 a.m. 3 may, 2021

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