Question
一个n个数码位的分数板，每一个数码位都是一个七段数码管，现在给出每个数码位的显示情况，问再点亮k段数码管的话能显示的最大的数是多少，如果不能构成一串数字，就输出-1
Solution
First
暴力搜索+剪枝(貌似中间用了一些记忆化搜索的思想？ 我不太懂 反正别人这么写的
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define maxn 1005
#define inf 0x3f3f3f
#define endl '\n'
#pragma GCC optimize(2)
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long ll;
//ll fpm(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
//ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
//ll fastPow(ll a,ll b) {ll res=1; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a;a=a*a;}return res;}
int n,k;
string ss[2050];
int ans[2050];
bool vis[2050][2050];
bool suc=0;
string s[10]={"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
void dfs(int now,int left)
{
if(now==n&&left==0){
suc=1;
return;
}
if(now==n){
return;
}
if(vis[now][left]){
return;
}
else{
vis[now][left]=1;
}
for(int i=9;i>=0;i--){
bool flag=0;
int cnt=0;
for(int j=0;j<9;j++){
if(ss[now][j]>s[i][j]){
flag=1;
break;
}
else if(ss[now][j]<s[i][j]){
cnt++;
}
}
if(!flag){
if(left>=cnt){
ans[now]=i;
dfs(now+1,left-cnt);
}
}
if(suc){
return;
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>ss[i];
}
dfs(0,k);
if(suc==0){
cout<<-1<<endl;
}
else{
for(int i=0;i<n;i++){
cout<<ans[i];
}
cout<<endl;
}
return 0;
}
Second
dp详见这篇博客
这篇博客写的很好 还能学到很多位运算知识
|=可以当作+=（线段树时候学过的忘了= =）
__builtin_popcount()可以把十进制整数化成二进制 然后返回其中1的个数