ZOJ 1428 Magazine Delivery
18740 단어 live
제목: 잡지 배달 을 담당 하 는 차 가 세 대 있 고 N 자리 L1 이 있 습 니 다. L2... LN, 차 가 Li 에서 Lj 로 이동 하 는 데 걸 리 는 시간 D [i] [j] 를 주 고 모든 위 치 를 배달 하 는 데 걸 리 는 최소 시간 을 구 합 니 다.
처음에는 세 대의 차 가 모두 L1 에 있 었 고 배달 할 때 는 한 대의 차 만 이동 할 수 있 었 으 며 나머지 두 개 는 제자리 에 있 었 다.그리고 위치 Li - 1 을 배달 해 야 Li 를 배달 할 수 있 습 니 다.
사고방식: DP
전달 공식:
D[i][j][k][m] = min(D[i - 1][x][k][m], D[i - 1][j][x][m], D[i - 1][j][k][x]) + time[x][i]; ( 1≤x＜i )
I 는 위치 i 가 사용 하 는 최소 시간, j 를 대표 합 니 다. k, m 는 각각 첫 번 째 차, 두 번 째 차, 세 번 째 차 의 위 치 를 대표 한다.
초기 조건 d [1] [1] [1] [1] = 0；
두 가지 도달 할 수 없 는 점 을 제거 합 니 다. 차 의 위치 가 i 보다 크 고 한 대의 차 가 없 는 위 치 는 i 와 같 습 니 다. 위치 i 에 도착 한 후에 반드시 한 대의 차 의 위치 가 i 에 있어 야 하기 때 문 입 니 다.
맨 앞 에 있 는 차 의 위치 가 i 이기 때문에 상 태 를 없 앨 수 있 습 니 다.
D[i][j][k] = min(D[i][j][k], D[i - 1][j][k] + time[i - 1][i]); //첫 차 를 옮기다
D[i][i - 1][k] = min(D[i][i - 1][k], D[i - 1][j][k] + time[j][i]); //두 번 째 차 를 옮기다
D[i][i - 1][j] = min(D[i][i - 1][j], D[i - 1][j][k] + time[k][i]); //세 번 째 차 를 옮기다
i 는 맨 앞 에 있 는 차 의 위치 이 고 j 는 다음 앞 이 며 k 는 마지막 이다.
4 상태의:
1 #include <cstdio>
2 #include <cstring>
3 #include <cstdlib>
4
5 const int MAXN = 30 + 5;
6 const int INF = 1 << 30;
7
8 int n;
9 int time[MAXN][MAXN];
10 int dp[MAXN][MAXN][MAXN][MAXN];
11
12 int min( int a, int b )
13 {
14 return a < b ? a : b;
15 }
16
17 int DP( int i, int j, int k, int m )
18 {
19 if ( i == 0 ) return 0;
20 if ( dp[i][j][k][m] != -1 ) return dp[i][j][k][m];
21 if ( j != i && k != i && m != i ) return dp[i][j][k][m] = INF; //
22 if ( j > i || k > i || m > i ) return dp[i][j][k][m] = INF; //
23
24 int MIN = INF;
25
26 for ( int x = 1; x < i; x++ )
27 {
28 int temp1 = DP( i - 1, x, k, m );
29 if ( temp1 < INF )
30 MIN = min( MIN, temp1 + time[i][x] );
31
32 int temp2 = DP( i - 1, j, x, m );
33 if ( temp2 < INF )
34 MIN = min( MIN, temp2 + time[i][x] );
35
36 int temp3 = DP( i - 1, j, k, x );
37 if ( temp3 < INF )
38 MIN = min( MIN, temp3 + time[i][x] );
39 }
40
41 return dp[i][j][k][m] = MIN;
42 }
43
44 int main()
45 {
46 int T;
47 scanf( "%d", &T );
48 while ( T-- )
49 {
50 scanf( "%d", &n );
51
52 for ( int i = 1; i < n; i++ )
53 for ( int j = i + 1; j <= n; j++ )
54 {
55 scanf( "%d", &time[i][j] );
56 time[j][i] = time[i][j];
57 }
58
59 memset( dp, -1, sizeof(dp) );
60 dp[1][1][1][1] = 0;
61
62 int MIN = INF;
63
64 for ( int x = 1; x < n; x++ )
65 for ( int y = 1; y < n; y++ )
66 {
67 MIN = min( MIN, DP( n, n, x, y ) );
68 MIN = min( MIN, DP( n, x, n, y ) );
69 MIN = min( MIN, DP( n, x, y, n ) );
70 }
71
72 printf( "%d
", MIN );
73 }
74
75 return 0;
76 }세 가지 상태의:
1 #include <cstdio>
2 #include <cstring>
3
4 const int MAXN = 35;
5
6 int time[MAXN][MAXN];
7 int dp[MAXN][MAXN][MAXN];
8
9 int min( int a, int b )
10 {
11 return a < b ? a : b;
12 }
13
14 int main()
15 {
16 int T;
17 scanf( "%d", &T );
18 while ( T-- )
19 {
20 int n;
21 scanf( "%d", &n );
22
23 memset( time, 0, sizeof(time) );
24 memset( dp, 0x7f, sizeof(dp) );
25
26 for ( int i = 1; i < n; i++ )
27 for ( int j = i + 1; j <= n; j++ )
28 {
29 scanf( "%d", &time[i][j] );
30 time[j][i] = time[i][j];
31 }
32
33 dp[1][1][1] = 0;
34 for ( int i = 2; i <= n; i++ )
35 for ( int j = 1; j < i; j++ )
36 for ( int k = 1; k < i; k++ )
37 {
38 dp[i][j][k] = min( dp[i][j][k], dp[i - 1][j][k] + time[i - 1][i] );
39 dp[i][i - 1][k] = min( dp[i][i - 1][k], dp[i - 1][j][k] + time[j][i] );
40 dp[i][i - 1][j] = min( dp[i][i - 1][j], dp[i - 1][j][k] + time[k][i] );
41 }
42
43 int MIN = 0x7fffffff;
44 for ( int i = 1; i < n; i++ )
45 for ( int j = 1; j < n; j++ )
46 MIN = min( MIN, dp[n][i][j] );
47
48 printf( "%d
", MIN );
49 }
50 return 0;
51 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
vvalive 6323 상태 압축 DP텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
