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;
}
