Atomic Car Race
2007.08.24 22:27 ACM/ICPC 2005
[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem F
[解説]
DAG (Directed Acyclic Graph)上の最短経路問題。動的計画法
詳細は後日書きたいと思います。
[サンプルプログラム]
[解説]
DAG (Directed Acyclic Graph)上の最短経路問題。動的計画法
詳細は後日書きたいと思います。
[サンプルプログラム]
001 #include<iostream> 002 #include<stdio.h> 003 #include<cfloat> 004 #include<algorithm> 005 using namespace std; 006 #define MAX 100 007 #define DMAX 10000 008 009 int D[MAX+1]; 010 double T[DMAX+1]; 011 double C[MAX+1]; 012 int n, r; 013 double b, v, e, f; 014 015 double getCost( int x ){ 016 if ( x >= r ) return 1/(v - e*(x - r)); 017 else return 1/(v - f*(r - x)); 018 } 019 020 void compute(){ 021 T[0] = 0.0; 022 for ( int x = 1; x <= D[n]; x++ ){ 023 T[x] = T[x-1] + getCost(x - 1); 024 } 025 026 for ( int i = 1; i <= n; i++ ) C[i] = FLT_MAX; 027 C[0] = 0.0; 028 for ( int i = 1; i <= n; i++ ){ 029 for ( int j = 0; j < i; j++ ){ 030 C[i] = min( C[i], C[j] + T[D[i] - D[j]] + (j == 0 ? 0 : b) ); 031 } 032 } 033 printf("%.4lf\n", C[n]); 034 } 035 036 bool input(){ 037 cin >> n; 038 if ( n == 0 ) return false; 039 D[0] = 0; 040 for ( int i = 1; i <= n; i++ ) cin >> D[i]; 041 cin >> b >> r >> v >> e >> f; 042 return true; 043 } 044 045 main(){ 046 while ( input() ) compute(); 047 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |