LED Display

向右看齐 2023-01-09 15:36 100阅读 0赞

## 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.  
![在这里插入图片描述][20210121210059967.png]  
**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

这道题的意思其实就是说一个LED灯“8”的样子，一共7个灯，只要熄了其中一个就不会再亮了，所以如果要表示某个数字，在这个数字的基础上再熄一个或多个仍然能表示其他的数字，比如说7，熄灭一个灯还能表示数字1，但再在1的基础上再熄灭的话就不能表示任何数字了，所以给你一串数字，问你至少需要多少个LED灯？匹配过程如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70]  
本题使用的是匈牙利算法，二分图，具体可参见下面链接的博客，写得很有意思而且很容易懂哈哈哈：  
[https://blog.csdn.net/u013384984/article/details/90718287][https_blog.csdn.net_u013384984_article_details_90718287]  
代码如下：

#include <cstdio>
    #include <cstring>
    #include <algorithm>
     
    using namespace std;
     
    const int MAX = 1005;
     
    int n;//序列中数字个数(二部图中左侧集合X和右侧集合Y中元素个数)
    //将序列中需要显示的数字存入数组num[i](二部图中左侧集合X和右侧集合Y中元素的值)
    //二维数组map为无环有向图对应的邻接矩阵
    int num[MAX], Map[MAX][MAX];
    //数组linker存储当前数字的上一个数字(即数字可由哪个数字转变而来) (对应于二部图中右侧元素所对应的左侧元素)
    //数组vis记录当前数字是否被访问过
    int linker[MAX], vis[MAX];
    
    //构造有向无环图
    //将每个数字可以到达的下一个数字化成一条路径，不能到达则说明自己是一条路径，构造有向无环图
    //假设num=[9,0,7,3]
    //9可到达7，故map[1][3]=1
    //注:下标从1开始
    void build() { 
        memset(Map, 0, sizeof(Map));//对邻接矩阵map进行初始化
     
        for (int i = 1; i < n; ++i) { 
            for (int j = i + 1; j <= n; ++j) { 
                if (num[i] == 0) { //数字可由0变为1或7
                    if (num[j] == 1) Map[i][j] = 1;
                    if (num[j] == 7) Map[i][j] = 1;
                } else if (num[i] == 3) { //数字可由3变为1或7
                    if (num[j] == 1) Map[i][j] = 1;
                    if (num[j] == 7) Map[i][j] = 1;
                } else if (num[i] == 4) { //数字可由4变为1
                    if (num[j] == 1) Map[i][j] = 1;
                } else if (num[i] == 6) { //数字可由6变为5
                    if (num[j] == 5) Map[i][j] = 1;
                } else if (num[i] == 7) { //数字可由7变为1
                    if (num[j] == 1) Map[i][j] = 1;
                }
    			//若数字为8，则全亮，可变为任意数字
    			//但根据题意，不能连续显示两个相同的数字，故8存在除到自身以外的9条路径
    			else if (num[i] == 8 &&
                           num[j] != 8) Map[i][j] = 1;
                else if (num[i] == 9) { //数字可由9变为1,3,4,5,7
                    if (num[j] == 1) Map[i][j] = 1;
                    if (num[j] == 3) Map[i][j] = 1;
                    if (num[j] == 4) Map[i][j] = 1;
                    if (num[j] == 5) Map[i][j] = 1;
                    if (num[j] == 7) Map[i][j] = 1;
                }
            }
        }
    }
    
    //寻找增广路径
    bool dfs (int u) { 
        for (int v = 1; v <= n; ++v) { 
    		//二部图左侧集合X到右侧集合Y有边并且该数字未被访问过
    		//num[u]到num[v]有边(数字num[u]可变为数字num[v])，并且num[v]未被访问过
            if (Map[u][v] && !vis[v]) { 
                vis[v] = 1;//记录状态为已访问(避免在寻找左侧元素的新匹配时重复访问该结点)
    			//如果暂无匹配(即直接匹配)
    			//或者原来匹配的左侧元素可以找到新的匹配(即可以找到一条增广路)
                if (linker[v] == -1 || dfs(linker[v])) { 
                    linker[v] = u;//当前左侧元素成为当前右侧元素的新匹配
                    return true;//返回匹配成功
                }
            }
        }
     
        return false;//循环结束，仍未找到匹配，返回匹配失败
    }
    
    //匈牙利算法寻找最大匹配
    int hungary () { 
        int res = 0;
        memset(linker, -1, sizeof(linker));//初始化linker数组(即置匹配M为空)
    	
    	//从左侧集合X中的第一个元素开始，对于每一个元素寻找增广路，若匹配成功，则匹配数加1。反之，匹配数不变。
    	//则最终匹配数即为最大匹配
        for (int u = 1; u <= n; ++u) { 
            memset(vis, 0, sizeof(vis));//重置vis数组
            if (dfs(u)) ++res;
        }
     
        return res;
    }
     
    int main() { 
    	
    	//输入序列中数字的个数n
        while(~scanf("%d", &n)) { 
    		//输入序列中n个数字的值，并存入数组num
            for (int i = 1; i <= n; ++i)
                scanf("%d", &num[i]);
    		//构造有向无环图
            build();
    		//执行匈牙利算法寻找最大匹配
    		//最小边覆盖=总结点数-最大匹配数
            printf("%d\n", n - hungary());
        }
     
        return 0;
    }

本题的debug录屏在可看以下链接的视频，可以帮助理解整个代码的运行过程：  
[https://www.bilibili.com/video/BV1ZX4y1K7U8][https_www.bilibili.com_video_BV1ZX4y1K7U8]

[20210121210059967.png]: /images/20221119/0c189f1408c64792a720d5d81b57f933.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70]: /images/20221119/0b8d56d496f24df3b887858645abb37b.png
[https_blog.csdn.net_u013384984_article_details_90718287]: https://blog.csdn.net/u013384984/article/details/90718287
[https_www.bilibili.com_video_BV1ZX4y1K7U8]: https://www.bilibili.com/video/BV1ZX4y1K7U8