aoj0611:Silk Road

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0611

解法

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