CF1341 D. Nastya and Scoreboard

Question

一个n个数码位的分数板，每一个数码位都是一个七段数码管，现在给出每个数码位的显示情况，问再点亮k段数码管的话能显示的最大的数是多少，如果不能构成一串数字，就输出-1.

Solution

1. 贪心+DFS+剪枝
   我们要构造的数最大，那就是高位尽可能大。直接爆搜TLE，考虑优化加入数组 $v\left[i\right]\left[j\right]$v[i][j]表示到第 $i$i个点，还剩 $j$j次操作的时候是否能找到可行解，若为true代表找不到可行解。
   $O(n\ast 10\ast 7)=O\left(140000\right)$O(n∗10∗7)=O(140000)一个点搜一次大概这个复杂度吧，可能常数有点大。
   跑了一下172ms。
   还可以进一步优化：
   预处理搜到 $mi\left[i\right]$mi[i]表示搜到第 $i$i个点之后所需要的最小值为多少， $ma\left[i\right]$ma[i]表示搜到第 $j$j个点之后所需要的最大值为多少，若剩余操作次数超出范围直接返回。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2000 + 5;

string s[N];
string num[10]={"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
bool flag=false,v[N][N];
int cnt=0;
int ans[N];
ll n,k;

inline bool check(int x,int y,int t){
	cnt=0;
	for(int i=0;i<7;i++){
		if(num[y][i]=='1'&&s[x][i]=='0') cnt++;
		else if(num[y][i]=='0'&&s[x][i]=='1') return false;
	}
	return cnt<=t?true:false;
}

void dfs(int x,int t){
	if(flag || t<0 || v[x][t]) return;
	if(x==n+1){
		if(t==0){
			flag=true;
			for(int i=1;i<=n;i++) cout<<ans[i];
		}
		return;
	}
	for(int i=9;i>=0;i--){
		if(!check(x,i,t)) continue;
		ans[x]=i;
		dfs(x+1,t-cnt);
	}
	if(!flag) v[x][t]=true;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	dfs(1,k);
	if(!flag) cout<<-1;
	return 0;
}

DFS+预处理优化(~为什么别人跑下来31ms我跑下来155ms因为我代码写的太辣鸡了~

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2000 + 5;

string s[N];
string num[10]={"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
bool flag=false,v[N][N];
int cnt=0;
int ans[N];
ll n,k;
int mi[N],ma[N];

inline bool check(int x,int y,int t){
	cnt=0;
	for(int i=0;i<7;i++){
		if(num[y][i]=='1'&&s[x][i]=='0') cnt++;
		else if(num[y][i]=='0'&&s[x][i]=='1') return false;
	}
	return cnt<=t?true:false;
}

inline void dfs(int x,int t){
	if(t>ma[x] || t<mi[x]) return;
	if(flag || t<0 || v[x][t]) return;
	if(x==n+1){
		if(t==0){
			flag=true;
			for(int i=1;i<=n;i++) cout<<ans[i];
		}
		return;
	}
	for(int i=9;i>=0;i--){
		if(!check(x,i,t)) continue;
		ans[x]=i;
		dfs(x+1,t-cnt);
	}
	if(!flag) v[x][t]=true;
}

void init(){
	for(int i=1;i<=n;i++){
		for(int j=9;j>=0;j--){
			if(!check(i,j,INF)) continue;
			ma[i]=max(ma[i],cnt);
			mi[i]=min(mi[i],cnt);
		}
	}
	for(int i=n;i>=1;i--){
		ma[i]+=ma[i+1];
		mi[i]+=mi[i+1];
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	init();
	dfs(1,k);
	if(!flag) cout<<-1;
	return 0;
}