题意:开灯,每个数字都由好几个灯组成,其中一些数字灭掉某些灯可以成为另一个数字,如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;
}