codeforces D. Nastya and Scoreboard

codeforces D. Nastya and Scoreboard"/>

codeforces D. Nastya and Scoreboard

题目

题意：

给你 n n n个 7 7 7位数，然后你可以尽力把木棍关闭的打开来使着 n n n个数字最大（只能从关闭->打开），问最大是多少。

思路

我们可以直接用 d f s dfs dfs先从最大的 9 9 9开始递归，然后因为无法从把打开的关闭，所以就有 ( v a l [ i ] & a [ s t e p ] ) = = a [ s t e p ] (val[i] \& a[step]) == a[step] (val[i]&a[step])==a[step]，这样可以保证 a s t e p a_{step} astep​上的位数在 v a l i val_i vali​都存在，就保证了只能打开了，然后 d f s ( s t e p + 1 , 剩 余 的 数 量 − 此 次 打 开 的 数 量 ) dfs(step+1,剩余的数量-此次打开的数量) dfs(step+1,剩余的数量−此次打开的数量)，因为使从最大的开始找的，所以一旦符合条件，那么这个就是答案了，但是数据有点大，所以需要加上剪枝，也就是 i f ( b o o k [ s t e p ] [ k k ] ) r e t u r n ; if(book[step][kk]) return ; if(book[step][kk])return; b o o k [ s t e p ] [ k k ] = t r u e ; book[step][kk] = true; book[step][kk]=true;这样的话，因为可能某些数字和某些数字翻转所需的使一样的，这样就会导致重复，因为已经递归过并且无法成功。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <deque>
#include <stack>
using namespace std;
typedef long long ll;
typedef vector<int> veci;
typedef vector<ll> vecl;
typedef pair<int, int> pii;
template <class T>
inline void read(T &ret) {char c;int sgn;if (c = getchar(), c == EOF) return ;while (c != '-' && (c < '0' || c > '9')) c = getchar();sgn = (c == '-') ? -1:1;ret = (c == '-') ? 0:(c - '0');while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');ret *= sgn;return ;
}
inline void out(int x) {if (x > 9) out(x / 10);putchar(x % 10 + '0');
}
const int maxn = 2010;
int val[20] = {119, 18, 93, 91, 58, 107, 111, 82, 127, 123}, a[maxn], ans[maxn];
int n, k, x;
bool book[maxn][maxn] = {false};
void dfs(int step, int kk) {if (kk < 0) return ;if (book[step][kk]) return ;book[step][kk] = true;if (step == n) {if (kk == 0) {for (int i = 0; i < n; i++) printf("%d", ans[i]);exit(0);}return ;}for (int i = 9; i >= 0; i--) {if ((val[i] & a[step]) == a[step]) {ans[step] = i;dfs(step + 1, kk - __builtin_popcount(val[i] ^ a[step]));}}
}
int main() {read(n) ,read(k);for (int i = 0; i < n; i++) {for (int j = 0; j < 7; j++) {scanf("%1d", &x);a[i] = (a[i] << 1) + x;}}dfs(0, k);printf("-1\n");return 0;
}