codeforces-1341D-Nastya and Scoreboard
传送门：https://codeforces.com/contest/1341/problem/D
题意：
一个n个数码位的分数板，每一个数码位都是一个七段数码管，现在给出每个数码位的显示情况，问再点亮k段数码管的话能显示的最大的数是多少，如果不能构成一串数字，就输出-1.
是一个加了许多剪枝的dfs
因为是要求能显示的最大的数是多少，所以应该从9往后贪心的选
记录下 cnt[i][j] 为第i个数想变成j需要点亮多少段数码管，如果变不成 cnt[i][j]=-inf
然后问题就转换成了 在cnt[i][j](i>=1&&i<=n)(j>=0&&j<=9) 的每一个 i 里选一个数，使他们相加恰好等于k，而且这个选择组成的n位数还是最大的
因为要求最大，所以越往前数应该往大了选，i==1时如果可以变成9，那就是9，9不行，就找8,7,6……，然后i==2，9,8,7……
那怎么实现，很眼熟，当年搜索不就是这么玩的吗
所以搞一个dfs就行
然后你就会Time limit exceeded on test 7
确实，n=2000呢，递归必超时呀
dfs(int n,int now（当前到了第几个数）,int ls（到现在为止已经点亮了多少数码管）,int k)
那就优化一下吧，首先ls>k指定是不行的（因为你想让他恰好等于k,你这都超了）
然后我们想，因为对于后面的每一个 i 都是要在 cnt[i][j] 里选一个出来
那如果剩下的k-ls小于（后面每一个 i 的 cnt[i][j] 最小值的和）是肯定不行的 ，这样即使后面每个数都取最小还是有i取不到数
同理，k-ls大于（后面每一个 i 的 cnt[i][j] 最大值的和）也不行，因为即使每个数都取最大k还是会剩下
upd:
cf怎么在重判后又填了几组数据
然后上面的就t掉了
不过填一个记忆化就好了（代码中的dp数组）
最后希望你们不要像我一样老犯憨批错误 快乐AC 乌拉~
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define lowbit(a) ((a)&-(a)) 5 #define clean(a,b) memset(a,b,sizeof(a)) 6 const int mod = 1e9 + 7; 7 const int inf=0x3f3f3f3f; 8 const int maxn = 2e7+10; 9 10 inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();} 11 int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;} 12 13 int _; 14 ////////////////////////////////////////////////////////////////////////// 15 int mp[2009][19]; 16 int d[19][19]; 17 int cnt[2009][19]; 18 int suma[2009],sumi[2009]; 19 int dp[2009][2009]; 20 vector<int>num; 21 int solve(int n,int now,int ls,int k) 22 { 23 if(ls>k) return 0; 24 if(k-ls<sumi[now]) return 0; 25 if(k-ls>suma[now]) return 0; 26 if(n==now-1&&ls==k) return 1; 27 else if(n==now-1&&ls!=k) return 0; 28 if(dp[now][ls]!=-1) return dp[now][ls]; 29 for(int i=9;i>=0;i--) 30 { 31 if(cnt[now][i]>=0) 32 { 33 // if(n-now>ls-cnt[now][i]) continue; 34 if(solve(n,now+1,ls+cnt[now][i],k)) 35 { 36 num.push_back(i); 37 return dp[now][ls]=1; 38 } 39 } 40 } 41 dp[now][ls]=0; 42 return 0; 43 } 44 ////////////////////////////////////////////////////////////////////////// 45 46 int main() 47 { 48 d[0][1]=1,d[0][2]=1,d[0][3]=1,d[0][5]=1,d[0][6]=1,d[0][7]=1; 49 d[1][3]=1,d[1][6]=1; 50 d[2][1]=1,d[2][3]=1,d[2][4]=1,d[2][5]=1,d[2][7]=1; 51 d[3][1]=1,d[3][3]=1,d[3][4]=1,d[3][6]=1,d[3][7]=1; 52 d[4][3]=1,d[4][4]=1,d[4][6]=1,d[4][2]=1; 53 d[5][1]=1,d[5][2]=1,d[5][4]=1,d[5][6]=1,d[5][7]=1; 54 d[6][1]=1,d[6][2]=1,d[6][4]=1,d[6][5]=1,d[6][6]=1,d[6][7]=1; 55 d[7][1]=1,d[7][3]=1,d[7][6]=1; 56 d[8][1]=1,d[8][2]=1,d[8][3]=1,d[8][4]=1,d[8][5]=1,d[8][6]=1,d[8][7]=1; 57 d[9][1]=1,d[9][2]=1,d[9][3]=1,d[9][4]=1,d[9][6]=1,d[9][7]=1; 58 int n=read(); 59 int k=read(); 60 for(int i=1;i<=n;i++) 61 { 62 for(int j=1;j<=7;j++) 63 scanf("%1d",&mp[i][j]); 64 } 65 for(int i=0;i<=2005;i++) 66 { 67 for(int j=0;j<=2005;j++) 68 { 69 dp[i][j]=-1; 70 } 71 } 72 for(int i=1;i<=n;i++) 73 { 74 for(int k=0;k<=9;k++) 75 { 76 for(int j=1;j<=7;j++) 77 { 78 if(d[k][j]==1&&mp[i][j]==0) cnt[i][k]++; 79 else if(d[k][j]==0&&mp[i][j]==1) cnt[i][k]=-inf; 80 } 81 } 82 } 83 for(int i=n;i>=1;i--) 84 { 85 int maxx=0,minn=7; 86 for(int j=0;j<=9;j++) 87 { 88 if(cnt[i][j]>=0) 89 { 90 minn=min(minn,cnt[i][j]); 91 maxx=max(maxx,cnt[i][j]); 92 } 93 } 94 suma[i]=suma[i+1]+maxx; 95 sumi[i]=sumi[i+1]+minn; 96 } 97 solve(n,1,0,k); 98 if(num.size()==0) printf("-1"); 99 for(int i=num.size()-1;i>=0;i--) printf("%d",num[i]); 100 printf(" "); 101 return 0; 102 }