ACM:LedDisplay

发表于 | 分类于 |
字数统计: 930 | 阅读时长 ≈ 5

LED Display

One day in the laboratory, Fred found some LED displays. This seven-segment LED can display digit 0 to 9 properly. But Fred soon find the LED have a serious problem, at the beginning, the seven bars were all on. But when one bar once was trun off, it can’t be turn on again! So ecah LED only can display digit in certain oder. For example, one LED can display 9,3,7 successively, but can’t display 2,4.
Now, Fred have a task to display a sequence of digit that is between 0 to 9. Because of the shortcoming of these LEDs, he need a number of them. But he also want to minimize the number, can you help him?
NOTE:If two digits in a sequece are the same,Fred want for the clearness, so he thought the latter digit can’t be displayed on the same LED.

Input:

The input consists of several test cases. The first line of each test case contains a positive integer N (<=1000), then followed by a list of N digits. Each digit follows with a blank space.

Output:

For each test case, you must print a minimum number of LED that Fred need in one line.

Sample Input:

1

8

4

9 0 7 3

8

8 8 8 9 6 5 4 1

Sample Output:

1

2

3

解题

(1) 思路：

首先先把数字之间的转换变为一张图，比如8能转换为0-9，则8到0-7，9各有一条边。7能转换为1。则7到1有一条边。 我们先用一个邻接矩阵把图表示出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
int convert[10][10]={
//0,1,2,3,4,5,6,7,8,9
    {0,1,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,1,0,0,0,0,0,1,0,0},
    {0,1,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,1,0,0,0,0},
    {0,1,0,0,0,0,0,0,0,0},
    {1,1,1,1,1,1,1,1,0,1},
    {0,1,0,1,1,1,0,1,0,0}
};

然后这题要求的是把所有的数字覆盖，然后路径最小。 这就是一个最小路径覆盖问题。

最小路径覆盖=n-最大匹配数。

这里考虑每条路径除了最后一个结点其它都有一个后续结点。 所有几个点没有尾结点，有有几条路径。 这里我们还需要让路径最小。所以需要让 pre->next的匹配数尽可能的多。

(2) 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstring>
#define MAXN 1010
using namespace std;

int data[MAXN];
int pre[MAXN];
int vis[MAXN];
int map[MAXN][MAXN];
int convert[10][10]={
//0,1,2,3,4,5,6,7,8,9
    {0,1,0,0,0,0,0,1,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,1,0,0,0,0,0,1,0,0},
    {0,1,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,1,0,0,0,0},
    {0,1,0,0,0,0,0,0,0,0},
    {1,1,1,1,1,1,1,1,0,1},
    {0,1,0,1,1,1,0,1,0,0}
};
int n;

//匈牙利算法
int find(int cur){//cur为当前起点
    for(int i=0; i<n; i++){ //被匹配的终点
        if(map[cur][i] && !vis[i]){//该终点未被匹配
            vis[i]=true;//这次匹配中，该终点已经被匹配了
            if(pre[i]==-1 || find(pre[i])){//该终点没有被匹配，或者被抢了的起点再去找一个终点
                pre[i]=cur;
                return 1;
            }
        }
    }
    return 0;
}

int main(){

    cin>>n;
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    memset(map,0,sizeof(map));
    for(int i=0;i<n;i++){
        cin>>data[i];
    }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(convert[data[i]][data[j]]==1){
                map[i][j]=true;
            }
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        memset(vis,0,sizeof(vis));
        ans+=find(i);
    }
    cout<<n-ans<<endl;
    return 0;
}

0%