zoj 2521 LED Display
zoj 2521 LED Display
用户1624346
发布于 2018-04-17 16:13:25
发布于 2018-04-17 16:13:25
题意：开灯，每个数字都由好几个灯组成，其中一些数字灭掉某些灯可以成为另一个数字，如0灭掉3个灯可以变成7，
现给你一组数字，如何组合可以形成最少的子序列（后面的数字可由前面灭灯形成）
分析：
错误思路
刚开始按照dp来做，d[len]表示当前的记录的灯是数字几，len表示已经形成了几个子序列，对于第j个数字，如果1-len之间没有数字可以变成
num[j]，则len++，d[len]=num[j]；这种思路错误的，根本无法保证其最优解，例如第一组测试数据9 0 7 3，若用该方法得到的结果是3，{9,7} {0} {3}
看了别人的题解，才知道这题是最小路径覆盖。。。。
若数字j可以由数字i变化而来，则数字i和j之间存在一条路径，则这样就成了最最小路径覆盖-n-最大匹配
这里最奇妙的就是判断j由数字i变化而来的方法，将每一笔画作为一个二进制的位数，若某笔画存在灯则相应的位值1，数字8其所有笔画的灯都亮着，所以8=（1111111）2=127
4=（1011001）=89
这里也可以用邻接表村，时间快了很多
邻接矩阵
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=1010;
int pre[MAXN];//记录[i]男生属于谁
int vis[MAXN];
int map[MAXN][MAXN];
int n,m;//男生，女生个数
int num[MAXN];
int r[10][10];
int dig[]={119,17,62,59,89,107,111,49,127,123};
void init()
{
int p,q;
for(int i=0; i<10; i++)
{
for(int j=0; j<10; j++)
{
if(i==j) r[i][j]=0;
else
{
p=dig[i],q=dig[j];
if((p|q)==p) r[i][j]=1;
else r[i][j]=0;
}
}
}
}
//匈牙利算法
int find(int cur)//cur为当前女生
{
int i;
for(i=1; 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()
{
int i,j,k;
int girl,boy;
int sum;
init();
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++) scanf("%d",&num[i]);
memset(pre,-1,sizeof(pre));
memset(map,0,sizeof(map));
sum=0;
for(i=1; i<n; i++)
{
for(j=i+1; j<=n; j++)
{
if(r[num[i]][num[j]]==1)map[i][j]=1;
else map[i][j]=0;
}
}
for(i=1; i<=n; i++) //女生去匹配男生
{
memset(vis,0,sizeof(vis));//每次重新标记0
sum+=find(i);
}
printf("%d\n",n-sum);
}
return 0;
}邻接表
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN=1010;
int pre[MAXN];//记录[i]男生属于谁
int vis[MAXN];
int n,m;//男生，女生个数
int num[MAXN];
int r[10][10];
int dig[]={119,17,62,59,89,107,111,49,127,123};
vector<int> G[MAXN];
void init()
{
int p,q;
for(int i=0; i<10; i++)
{
for(int j=0; j<10; j++)
{
if(i==j) r[i][j]=0;
else
{
p=dig[i],q=dig[j];
if((p|q)==p) r[i][j]=1;
else r[i][j]=0;
}
}
}
}
int find(int cur)
{
for(int i=0,q; i <G[cur].size(); i++)
if(!vis[q=G[cur][i]])
{
vis[q]=1;
if(pre[q]==-1|| find(pre[q]))
{
pre[q]=cur;
return 1;
}
}
return 0;
}
int main()
{
int i,j,k;
int sum;
init();
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%d",&num[i]);
G[i].clear();
}
memset(pre,-1,sizeof(pre));
sum=0;
for(i=1; i<n; i++)
{
for(j=i+1; j<=n; j++)
{
if(r[num[i]][num[j]]==1) G[i].push_back(j);
}
}
for(i=1; i<=n; i++) //女生去匹配男生
{
memset(vis,0,sizeof(vis));//每次重新标记0
sum+=find(i);
}
printf("%d\n",n-sum);
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2013-03-07 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读