第一次做洛谷系列，緊張，請多關(guān)照哦

題目傳送門：[SDOI2007] 科比的比賽 - 洛谷

?

思路分析

這道題大概題意是給定我們的主人公 Kobe Bryant 的 mm 個對手，nn 場比賽相對應(yīng)的獲勝概率。求 Kobe Bryant 最大全部獲勝概率和打敗對手能力值之和。

這道題可以使用 dfs 的思路解決。但是 Kobe Bryant 的對手非常多（也就是 mm 的值非常大），直接搜索的時間復(fù)雜度肯定非常高，就需要一些有效的剪枝。

最容易想到的是最優(yōu)性剪枝，也就是如果當(dāng)目前答案已經(jīng)不優(yōu)于已經(jīng)存在的答案就可以直接放棄這個答案。

具體來說就是在 dfs 函數(shù)中加入：

if(cmp_double(tmp1,ans1)==0) return;

但是這樣的優(yōu)化顯然是明顯不夠的。

這個題目有一個寫的很明顯特性是 n≤mn≤m。由于 nn 的值很小，而 Kobe Bryant 在每場比賽只能對戰(zhàn)一個對手，所以 Kobe Bryant 只需要對戰(zhàn) nn 個對手并不是 mm 個。翻譯成白話文就是 Kobe Bryant 可以只找弱的打，也就是找成功概率高的打。根據(jù)這個特性，我們可以在搜索時只搜前 nn 弱的對手。也可以理解這個剪枝是貪心的思路，因此 Kobe Bryant 的對手就少了很多。再根據(jù)前一條剪枝可以拿到 4040 分。

最后考慮到的是可以使用啟發(fā)式搜索剪枝優(yōu)化，對當(dāng)前的結(jié)果進行估計，也就是即使是當(dāng)前狀態(tài)的最優(yōu)情況，目前 Kobe Bryant 的獲勝概率仍然沒有已有最優(yōu)情況高的時候舍棄。為了保證估計的效率，可以使用預(yù)處理的方式讓每次詢問復(fù)雜度降到 O(n)O(n)。

進行以上三次優(yōu)化的思路是已經(jīng)可以通過本題了。

代碼

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define antirep(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e6,M=1e3;
const double err=1e-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-y>err) return 1;if(x-y<err) 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.p>y.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[i+1]*k[i][1].p;
}
void dfs(int cur,double tmp1,int tmp2){if(cur>n){if(cmp_double(tmp1,ans1)==1||cmp_double(tmp1,ans1)==2){ans1=tmp1;if(tmp2>ans2) ans2=tmp2;}return;}if(cmp_double(tmp1,ans1)==0) return;if(f(cur,tmp1)==0)return;rep(i,1,n){int ID=k[cur][i].id;if(vst[ID]==1) continue;vst[ID]=1;tmp1*=k[cur][i].p,tmp2+=a[ID];dfs(cur+1,tmp1,tmp2);tmp1/=k[cur][i].p,tmp2-=a[ID],vst[ID]=0;}return;
}
signed main(){cin>>n>>m;rep(i,1,m) cin>>a[i];rep(i,1,n){rep(j,1,m)cin>>k[i][j].p,k[i][j].id=j;sort(k[i]+1,k[i]+1+m,cmp);}prepare();dfs(1,1,0);cout<<fixed<<setprecision(12)<<ans1<<endl;cout<<ans2<<endl;return 0;
}

這里對代碼進行一些解釋，因為本題是浮點數(shù)操作，浮點數(shù)會在精度很高的時候產(chǎn)生誤差，因此這里使用了 cmp_double 函數(shù)進行比較浮點數(shù)大小。

預(yù)處理之所以是逆序的儲存是因為正序的搜索每次詢問的都是剩余比賽的最有情況。

排序可以保證把 Kobe Bryant 最弱（也就是獲勝概率最高）的對手放在每場比賽的最前面。

后記

備注：Kobe Bryant 是本題主人公科比的原名。而在 20202020 年，科比本人乘坐的西科斯基 S?76S?76 直升機在美國加利福尼亞州洛杉磯縣卡拉巴薩斯市墜毀。年僅 4141 歲。

雖然我們不能跟題目重所描述的那樣幫助科比贏得比賽,但是我們可以通過解出這道題淡化對科比離去的哀傷。

牢大，我想你了。