思维——Nastya and Scoreboard"/>
思维——Nastya and Scoreboard
传送门
题解:
定义 f ( i , j ) f(i,j) f(i,j)函数搜索到第i个字符的时候使用了j根木棍。我们可以将题目中的10个字符串全部转换成十进制,然后因为我们要想办法变成这10个数字,所以我们从大到小搜索过去,并且记录已经搜索的情况进行剪纸。
#include <bits/stdc++.h>
//#define int long long
using namespace std;
int tab[]={119,18,93,91,58,107,111,82,127,123};
int f[2005][2005],n,k,a[2005],res[2005];
int work(int x)
{int res=0;for(int i=7;i>=0;i--){if(x>>i&1) res++;}return res;
}
void dfs(int x,int us)
{if(f[x][us]||us>k) return ;f[x][us]=1;if(x==n+1){if(us==k){for(int i=1;i<=n;i++) printf("%d",res[i]);exit(0);}return;}for(int i=9;i>=0;i--){res[x]=i;if((tab[i]&a[x])==a[x]) dfs(x+1,us+work(a[x]^tab[i]));}
}
signed main()
{string s;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){cin>>s;for(int j=0;j<s.length();j++){a[i]=(a[i]<<1)+(s[j]-'0');}}dfs(1,0);puts("-1");
}
更多推荐
思维——Nastya and Scoreboard
发布评论