第１４回日本情報オリンピック 予選（オンライン） D-シルクロード(Silk Road)

問題

atcoder.jp

考察

一見してDPです。

ちょっと前までは怖気づいてしまって手が出ない類の問題でしたが，EDPCの前半をこなした私は昨日までの私とは違います。

とにかく書いてみることにしました。

まずはDPテーブルをどう組むか。

m日目にnにいるときの疲労度の最小値をdp[m][n]としました。
０日目に０にいるときはdp[0][0]=０、その他のところはINFで初期化します。

m日目にnにいる、ということは、その前の日からnにいて待機していたかm日目の移動でnに来たかのいずれかです。

前の日からnにいた場合

dp[m][n]=min(dp[m][n],dp[m-1][n]);

m日目の移動でnに来た場合

疲労度　d[n]*c[m」が蓄積されます。
また０日目の場合は移動してないのでif(n>0)の場合のみこの遷移が生じます。

dp[m][n]=min(dp[m][n],dp[m-1][n-1]+d[n]*c[m]);

DPテーブルを回します。

０オリジンと１オリジンが微妙に悩ましく、試行錯誤しながら決めました。

テストケース、すんなりACできて感激です。

提出コード

#include <bits/stdc++.h>
using namespace std;
static const int INF=1000000000;

int main(){
  int N,M;
  cin>>N>>M;
  int d[N+1];
  int c[M+1];
  for(int i=0;i<N;i++){
    cin>>d[i+1];
  }
  for(int i=0;i<M;i++){
    cin>>c[i+1];
  }  
  int dp[1010][1010];
  for(int i=0;i<1010;i++){
    for(int j=0;j<1010;j++){
      dp[i][j]=INF;
    }
  }
  dp[0][0]=0;
  for(int m=1;m<=M;m++){
    for(int n=0;n<=N;n++){
      dp[m][n]=min(dp[m][n],dp[m-1][n]);
      if(n>0){
        dp[m][n]=min(dp[m][n],dp[m-1][n-1]+d[n]*c[m]);
      }
    }
  }
  cout<<dp[M][N]<<endl;
  return 0;
}