此题搜索可以过!!!
看到此题,第一想法,是01背包,然而,作为一个蒟蒻,我怎么会打正解呢?,于是就开始打dfs!
想要完成此题,普通的搜索肯定是过不了的(不然要dp干嘛),所以,我们要考虑
剪枝
比较容易的,我们可以轻松想出来剪枝:
(不吐槽名字我们还是好朋友。。。)
1.用数组guji[i]表示搜索到i时,不考虑智商,情商必须大于零的限制,之后能获得的最大智,情商之和。如果当前搜索到的智,情商之和加上guji[i]任然小于等于已经搜出来的ans,那么,当前的状态一定不是最优的(这属于最优性优化)
2.用数组jiuzi表示搜索到i时,不考虑其他限制,之后能获得的最大的智商。如果当前搜索到的智商加上jiuz[i]任然小于0,那么,当前状态一定不满足智商必须大于零的限制。
3.用数组jiuq[i]表示搜索到i时,不考虑其他限制,之后能获得的最大的情商。同2
然后。。。你就A了。。。测试速度25ms。。。(orz)
代码:
//#pragma GCC optimize()//手动Ox优化 #include<bits/stdc++.h> using namespace std; const int N=402;//记得多开1位,因为要访问n+1 int z[N],q[N]; int ans=0; int n; int guji[N],jiuz[N],jiuq[N]; inline void dfs(int now,int zh,int qh){ if(zh+qh+guji[now]<=ans){ return; } if(zh+jiuz[now]<0){ return; } if(qh+jiuq[now]<0){ return; } if(now==n+1){//如果搜索到底 ans=zh+qh;//由于当前答案一定最优,直接赋值 return; } dfs(now+1,zh+z[now],qh+q[now]); dfs(now+1,zh,qh); } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d%d",&z[i],&q[i]); } for(int i=n;i>=1;--i){ guji[i]=guji[i+1]; jiuz[i]=jiuz[i+1],jiuq[i]=jiuq[i+1]; if(z[i]>0){//如果智商大于0 jiuz[i]+=z[i];//智商可取最大值加上z[i] } if(q[i]>0){ jiuq[i]+=q[i];//情商可取最大值加上q[i] } if(z[i]+q[i]>0){//如果和大于零 guji[i]+=z[i]+q[i];//最大值加上z[i]+q[i] } } dfs(1,0,0); cout<<ans; return 0; } /** * ┏┓ ┏┓+ + * ┏┛┻━━━┛┻┓ + + * ┃ ┃ * ┃ ━ ┃ ++ + + + * ████━████+ * ◥██◤ ◥██◤ + * ┃ ┻ ┃ * ┃ ┃ + + * ┗━┓ ┏━┛ * ┃ ┃ + + + +Code is far away from * ┃ ┃ + bug with the animal protecting * ┃ ┗━━━┓ 神兽保佑,代码无bug * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ + + + + * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛+ + + + */