AOJ 0530 Pyon-Pyon River Crossing
今日はJOI予選です。5完を目指します
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0530
解法
動的計画法をつかう
横の列の個数分の配列をとるとTLEしそう。
そこで、一つの行には石がたかだか10個しかないという制約を利用するとはやくなる
#include <cstdio> #include <algorithm> #include <vector> using namespace std; typedef long long ll; typedef pair<ll, ll> P; const ll INF = 100000000000000; ll dan(P p1, P p2){ return (p1.second + p2.second) * abs(p2.first - p1.first); } int main(){ ll n, m; while(true){ scanf("%lld %lld", &n, &m); if(n == 0) break; vector<P> a[n + 1]; ll dp[n + 1][10][m + 1]; //初期化 for(int i = 0; i <= n; i++) for(int j = 0; j < 10; j++) for(int k = 0; k < m + 2; k++) dp[i][j][k] = (i==0 || i==1)?0:INF; for(int i = 1; i <= n; i++){ int ki; scanf("%d", &ki); for(int j = 0; j < ki; j++){ ll x, d; scanf("%lld %lld", &x, &d); a[i].push_back(P(x, d)); } } for(int i = 2; i <= n; i++){ for(int j = 0; j < a[i].size(); j++){ for(int k = m; k >= 0; k--){ ll t = INF; for(int l = 0; l < a[i-1].size(); l++) t = min(t, dan(a[i-1][l], a[i][j]) + dp[i-1][l][k]); if(k < m){ if(i == 2)t = 0; for(int l = 0; l < a[i-2].size(); l++){ t = min(t, dan(a[i-2][l], a[i][j]) + dp[i-2][l][k + 1]); } t = min(t, dp[i][j][k + 1]); } dp[i][j][k] = t; } } } /* for(int i = 0; i <= n; i++){ printf("%d| ", i); for(int j = 0; j < a[i].size(); j++){ printf(" %lld", dp[i][j][1]); } puts(""); } */ ll ans = INF; for(int j = 0; j < a[n].size(); j++) ans = min(ans, dp[n][j][0]); if(m >= 1) for(int j = 0; j < a[n-1].size(); j++) ans = min(ans, dp[n-1][j][1]); printf("%lld\n", ans); } return 0; }