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

題目傳送門(mén)：[SDOI2007] 科比的比賽 - 洛谷

?

思路分析

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

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

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

具體來(lái)說(shuō)就是在 dfs 函數(shù)中加入：

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

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

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

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

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

代碼

#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;
}

這里對(duì)代碼進(jìn)行一些解釋，因?yàn)楸绢}是浮點(diǎn)數(shù)操作，浮點(diǎn)數(shù)會(huì)在精度很高的時(shí)候產(chǎn)生誤差，因此這里使用了 cmp_double 函數(shù)進(jìn)行比較浮點(diǎn)數(shù)大小。

預(yù)處理之所以是逆序的儲(chǔ)存是因?yàn)檎虻乃阉髅看卧儐?wèn)的都是剩余比賽的最有情況。

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

后記

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

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

牢大，我想你了。