codeforces D. Nastya and Scoreboard
程序员文章站
2022-06-08 16:01:04
...
题目
题意:
给你个位数,然后你可以尽力把木棍关闭的打开来使着个数字最大(只能从关闭->打开),问最大是多少。
思路
我们可以直接用先从最大的开始递归,然后因为无法从把打开的关闭,所以就有,这样可以保证上的位数在都存在,就保证了只能打开了,然后,因为使从最大的开始找的,所以一旦符合条件,那么这个就是答案了,但是数据有点大,所以需要加上剪枝,也就是这样的话,因为可能某些数字和某些数字翻转所需的使一样的,这样就会导致重复,因为已经递归过并且无法成功。
#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;
}
推荐阅读
-
Codeforces486 D. Valid Sets(树形dp,去重技巧)
-
Codeforces Round #656 (Div. 3)D. a-Good String(递归+dfs)
-
Educational Codeforces Round 97 (Rated for Div. 2) D. Minimal Height Tree
-
Codeforces Round #665 (Div. 2) D. Maximum Distributed Tree(dfs)
-
Codeforces Round #619 (Div. 2) D. Time to Run
-
Codeforces Round #583 (Div. 1 + Div. 2,) D. Treasure Island(dfs+思维)
-
[codeforces]round670 D. Three Sequences
-
Codeforces(D. 505)状压DP
-
codeforces D. Game With Array
-
Codeforces Round #533 (Div. 2) D. Kilani and the Game(bfs+模拟)