aoj0611:Silk Road
解法
DPで解いた。
dp[i][j]:i日過ぎたときに町jにいる場合の最少の疲れ
とする。すると漸化式は
dp[0][0]=0; dp[i][j]=INF (i<j) dp[i+1][j+1]=min(dp[i][j+1],dp[i][j]+d[j]*c[i]); (i<=j)
となる。
ある町xに行くための方法は、既にxにいる場合とx-1から移動する場合の2通りあるのでそれらの疲れの最少値を求めている。
ついでに配列を使いまわすとよい。
コード
#include<bits/stdc++.h> using namespace std; const int INF=1e9; int n,m,d[1000],c[1000]; int dp[2000]; int main(){ cin>>n>>m; for(int i=0;i<n;i++)cin>>d[i]; for(int i=0;i<m;i++)cin>>c[i]; fill_n(dp,n+1,INF); dp[0]=0; for(int i=0;i<m;i++){ for(int j=n-1;j>=0;j--){ dp[j+1]=min(dp[j+1],dp[j]+d[j]*c[i]); } } cout<<dp[n]<<endl; return 0; }