2022/06/12 內積

2022.12.02 PM 00:30 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=i402
出題者 : 2022年6月APCS
標籤 : DP(Dynamic Programming, 動態規劃)
難易度 : 4

解題想法 : 
想寫出一個良好的DP程式，首先最重要的就是定義。

-定義-
根據題意，我們可以定義dp[i][j]為，當a以i結尾且b以j結尾時所能得到的最大內積。

-基底狀態-
內積計算的條件是a,b選出的子陣列長度相同，因此當i(j)等於0時，表示a(b)只選出一個數字，也就是說對於每個a[i](b[j])都沒得選，只能跟b[0](a[0])乘，故dp[i][0]的最大值(唯一值)必為a[i]*b[0]，且dp[0][j]的值必為a[0]*b[j]。

-轉移式-
假如此時想求出dp[i][j]的值，我們會有下列兩種轉移狀態 :
1. dp[i-1][j-1]的值小於等於0，加上他不會更好，所以還不如不要繼承，所以 dp[i][j] = a[i]*b[j]
2. dp[i-1][j-i]的值大於0，因此可以繼承它的值(加了它值會變大)，則 dp[i][j] = 
dp[i-1][j-1] + a[i]*b[j]
實作上我們可以先讓dp[i-1][j-1]和0取max，並將結果跟a[i]*b[j]相加，即可一次滿足1.和2.的需求。

-走訪-
for i from 0~n-1 {
    dp[i][0] = a[i]*b[j]
}
for i from 0~m-1 {
    dp[0][i] = a[0]*b[i]
}
for i from 1~n-1 {
    for j from 1~m-1 {
        dp[i][j] = 
            max(dp[i-1][j-1],0) + a[i]*b[j]                 
    }
}
for i from 0~n-1 {
    for j from 0~m-1 {
        ans = max(ans,dp[i][j])
    }
}

※記得要把a(或b)翻轉再做一次

※參考自 吳邦一 教授此影片(推薦!) : https://www.youtube.com/watch?v=EvyyRNAnAtE

//C++ language

#include<iostream>
#include<vector> //vector
#include<algorithm> //max(), reverse()
#include<cstring> //memset()
using namespace std;
int n,m,x,ans=-1e9;
vector<int>a,b;
int dp[1005][1005]={0};
void init(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>x;
        a.push_back(x);
    }
    for(int i=0;i<m;i++){
        cin>>x;
        b.push_back(x);
    }
}
void solve(){
    for(int i=0;i<n;i++){
        dp[i][0]=a[i]*b[0];
    }
    for(int i=0;i<m;i++){
        dp[0][i]=a[0]*b[i];
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            dp[i][j]=max(dp[i-1][j-1],0)+a[i]*b[j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            ans=max(ans,dp[i][j]);
        }
    }
}
void output(){
    cout<<ans<<"\n";
}
int main(){
    init();
    solve();
    memset(dp,0,sizeof(dp));
    reverse(a.begin(),a.end());
    solve();
    output();
    return 0;
}

相關文章

分享此文：