国内网站设计案例欣赏,黑帽seo优化,北京公司核名工商官网,网站域名有什么用第一次做洛谷系列#xff0c;紧张#xff0c;请多关照哦
题目传送门#xff1a;[SDOI2007] 科比的比赛 - 洛谷 思路分析
这道题大概题意是给定我们的主人公 Kobe Bryant 的 mm 个对手#xff0c;nn 场比赛相对应的获胜概率。求 Kobe Bryant 最大全部获胜概率和打败对手能…第一次做洛谷系列紧张请多关照哦
题目传送门[SDOI2007] 科比的比赛 - 洛谷 思路分析
这道题大概题意是给定我们的主人公 Kobe Bryant 的 mm 个对手nn 场比赛相对应的获胜概率。求 Kobe Bryant 最大全部获胜概率和打败对手能力值之和。
这道题可以使用 dfs 的思路解决。但是 Kobe Bryant 的对手非常多也就是 mm 的值非常大直接搜索的时间复杂度肯定非常高就需要一些有效的剪枝。
最容易想到的是最优性剪枝也就是如果当目前答案已经不优于已经存在的答案就可以直接放弃这个答案。
具体来说就是在 dfs 函数中加入
if(cmp_double(tmp1,ans1)0) return;但是这样的优化显然是明显不够的。
这个题目有一个写的很明显特性是 n≤mn≤m。由于 nn 的值很小而 Kobe Bryant 在每场比赛只能对战一个对手所以 Kobe Bryant 只需要对战 nn 个对手并不是 mm 个。翻译成白话文就是 Kobe Bryant 可以只找弱的打也就是找成功概率高的打。根据这个特性我们可以在搜索时只搜前 nn 弱的对手。也可以理解这个剪枝是贪心的思路因此 Kobe Bryant 的对手就少了很多。再根据前一条剪枝可以拿到 4040 分。
最后考虑到的是可以使用启发式搜索剪枝优化对当前的结果进行估计也就是即使是当前状态的最优情况目前 Kobe Bryant 的获胜概率仍然没有已有最优情况高的时候舍弃。为了保证估计的效率可以使用预处理的方式让每次询问复杂度降到 O(n)O(n)。
进行以上三次优化的思路是已经可以通过本题了。
代码
#includebits/stdc.h
#define int long long
#define rep(i,a,b) for(int ia;ib;i)
#define antirep(i,a,b) for(int ia;ib;i--)
using namespace std;
const int N1e6,M1e3;
const double err1e-10;
bool vst[N];
double ans1,pr[N],Gl[N];
int n,m,a[N],ans2;
struct node{int id;double p;}k[M][M];
int cmp_double(double x,double y){if(abs(x-y)err) return 2;if(x-yerr) return 1;if(x-yerr) return 0;return 0x7fffffff;
}
bool cmp(node x,node y){if(cmp_double(x.p,y.p)2) return a[x.id]a[y.id];return x.py.p;
}
int f(int cur,double tmp1){return cmp_double(tmp1*pr[cur],ans1);
}
void prepare(){pr[n]k[n][1].p;antirep(i,n-1,1)pr[i]pr[i1]*k[i][1].p;
}
void dfs(int cur,double tmp1,int tmp2){if(curn){if(cmp_double(tmp1,ans1)1||cmp_double(tmp1,ans1)2){ans1tmp1;if(tmp2ans2) ans2tmp2;}return;}if(cmp_double(tmp1,ans1)0) return;if(f(cur,tmp1)0)return;rep(i,1,n){int IDk[cur][i].id;if(vst[ID]1) continue;vst[ID]1;tmp1*k[cur][i].p,tmp2a[ID];dfs(cur1,tmp1,tmp2);tmp1/k[cur][i].p,tmp2-a[ID],vst[ID]0;}return;
}
signed main(){cinnm;rep(i,1,m) cina[i];rep(i,1,n){rep(j,1,m)cink[i][j].p,k[i][j].idj;sort(k[i]1,k[i]1m,cmp);}prepare();dfs(1,1,0);coutfixedsetprecision(12)ans1endl;coutans2endl;return 0;
}
这里对代码进行一些解释因为本题是浮点数操作浮点数会在精度很高的时候产生误差因此这里使用了 cmp_double 函数进行比较浮点数大小。
预处理之所以是逆序的储存是因为正序的搜索每次询问的都是剩余比赛的最有情况。
排序可以保证把 Kobe Bryant 最弱也就是获胜概率最高的对手放在每场比赛的最前面。
后记
备注Kobe Bryant 是本题主人公科比的原名。而在 20202020 年科比本人乘坐的西科斯基 S−76S−76 直升机在美国加利福尼亚州洛杉矶县卡拉巴萨斯市坠毁。年仅 4141 岁。
虽然我们不能跟题目重所描述的那样帮助科比赢得比赛,但是我们可以通过解出这道题淡化对科比离去的哀伤。
牢大我想你了。
