#37426: 求解為啥一直90分


shane950517@gmail.com (ㄟ不是)

學校 : 國立臺中高級工業職業學校
編號 : 166971
來源 : [60.249.14.165]
最後登入時間 :
2024-02-28 10:14:56
i402. 4. 內積 -- 2022年6月APCS | From: [122.118.13.60] | 發表日期 : 2023-09-08 02:37

#include <iostream>
#include <algorithm>
#include <array>
using namespace std;

int inf = 1e9;
array<int, 1005> A, B;

int dp(int p, int n, int m) {
    int sum = 0, ans = -inf;
    for (int i = 1; i <= m; i++) {
        if (i + p < 1 || i + p > n) continue;
        sum += A[i + p] * B[i];
        ans = max(sum, ans), sum = max(sum, 0);
    }
    return ans;
}

int main() {
    int n, m, ans = -inf;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> A[i];
    for (int i = 1; i <= n; i++) cin >> B[i];
    for (int i = 1 - m; i <= n; i++) ans = max(ans, dp(i, n, m));
    for (int i = 1; i <= m >> 1; i++) swap(B[i], B[m - i + 1]);
    for (int i = 1 - m; i <= n; i++) ans = max(ans, dp(i, n, m));
    cout << ans << '\n';
    return 0;
}

 
ZeroJudge Forum