DP URAL 1119 메트로
7267 단어 metro
제목 전송문
1 /* 2 : (1,1), (n,m); +1, k +sqrt (2.0); 3 DP: JayYe, , :) 4 , , 5 */ 6 #include <cstdio> 7 #include <iostream> 8 #include <algorithm> 9 #include <cmath> 10 #include <cstring> 11 using namespace std; 12 13 const int MAXN = 1e3 + 10; 14 const int INF = 0x3f3f3f3f; 15 double dp[MAXN][MAXN]; 16 int used[MAXN][MAXN]; 17 int a[MAXN][MAXN]; 18 19 int main(void) //URAL 1119 Metro 20 { 21 freopen ("C.in", "r", stdin); 22 23 int n, m, k; 24 while (scanf ("%d%d", &n, &m) == 2) 25 { 26 scanf ("%d", &k); 27 int u, v; 28 memset (used, 0, sizeof (used)); 29 while (k--) {scanf ("%d%d", &u, &v); used[u][v] = true;} 30 31 for (int i=0; i<=n; ++i) 32 { 33 for (int j=0; j<=m; ++j) 34 { 35 if (!i && !j) dp[i][j] = 0; 36 else if (!i) dp[1][j] = dp[1][j-1] + 1; 37 else if (!j) dp[1][j] = dp[0][j] + 1; 38 else dp[1][j] = min (dp[1][j-1], dp[0][j]) + 1; 39 if (used[i][j]) dp[1][j] = min (dp[0][j] + 1, dp[0][j-1] + sqrt (2.0)); 40 } 41 } 42 43 printf ("%.0f
", dp[1][m] * 100); 44 45 } 46 47 return 0; 48 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
DP URAL 1119 메트로텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.