UVa 10131 - Is Bigger Smarter?

DAG 최대 경로;
AC 이후에 검색해 봤는데 몇 개는 최대 하강 서열로 이해했지만 dp의 연습 문제로서 DAG로 바뀌었고 복잡도는 당연히 높았지만 시간을 초과하지 않았다.

 1 # include <stdio.h>
 2 
 3 int n;
 4 int w[1000];
 5 int s[1000];
 6 int d[1000];
 7 int g[1000][1000];
 8 
 9 int dp(int i);
10 void print_list(int i);
11 
12 int main()
13 {
14     int i, j, maxl, k;
15     
16     n = 1;
17     while (~scanf("%d%d", &w[n], &s[n]))
18         ++n;
19        --n;
20        for (i = 1; i <= n; ++i)
21        for (j = 1; j <= n; ++j)
22            if (w[i]<w[j] && s[i]>s[j])
23                g[i][j] = 1;
24     maxl = 0;
25     for (i = 1; i <= n; ++i)
26         if (maxl < dp(i)) {maxl = d[i]; k = i;}
27        
28        printf("%d
", maxl+1);
29        print_list(k);
30     
31     return 0;
32 }
33 
34 int dp(int i)
35 {
36     int j;
37     if (d[i] > 0) return d[i];
38     d[i] = 0;
39     for (j = 1; j <= n; ++j)
40         if (g[i][j] && d[i]<dp(j)+1) d[i] = d[j]+1;
41        return d[i];
42 }
43 void print_list(int i)
44 {
45     int j;
46     printf("%d
", i);
47     for (j = 1; j <= n; ++j)
48         if (g[i][j] && d[i] == d[j]+1)
49            {
50                print_list(j);
51                break;
52         }
53 }

생각해 보니 건도의 과정을 생략하고 직접 판단하면 된다.

 1 # include <stdio.h>
 2 
 3 int n;
 4 int w[1000];
 5 int s[1000];
 6 int d[1000];
 7 
 8 int dp(int i);
 9 void print_list(int i);
10 
11 int main()
12 {
13     int i, j, maxl, k;
14         
15     n = 1;
16     while (~scanf("%d%d", &w[n], &s[n]))
17         ++n;
18        --n;
19     maxl = 0;
20     for (i = 1; i <= n; ++i)
21         if (maxl < dp(i)) {maxl = d[i]; k = i;}
22        
23        printf("%d
", maxl+1);
24        print_list(k);
25     
26     return 0;
27 }
28 
29 int dp(int i)
30 {
31     int j;
32     if (d[i] > 0) return d[i];
33     d[i] = 0;
34     for (j = 1; j <= n; ++j)
35         if (w[i]<w[j] && s[i]>s[j] && d[i]<dp(j)+1) d[i] = d[j]+1;
36        return d[i];
37 }
38 void print_list(int i)
39 {
40     int j;
41     printf("%d
", i);
42     for (j = 1; j <= n; ++j)
43         if (w[i]<w[j] && s[i]>s[j] && d[i] == d[j]+1)
44            {
45                print_list(j);
46                break;
47         }
48 }

이렇게 하면 적지 않은 공간을 절약하지만 시간의 복잡도는 변하지 않는다(O(n*n).

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

UVA - 10986 Sending email(Dijkstra 인접 테이블 + 우선 순위 대기열 최적화)

제목 대의: s점에서 t점까지의 최소 거리를 구하는 그림을 주세요. 확인: 적나라한 최단길이지만 n이 너무 크면 인접 행렬을 사용할 수 없기 때문에 Dijkstra에 대한 인접표 + 우선 대기열 최적화가 필요합니다....

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

UVa 10131 - Is Bigger Smarter?

좋은 웹페이지 즐겨찾기