[DFS]JZOJ 2941 贿赂

￡神魔★判官ぃ 2021-12-16 01:07 162阅读 0赞

#### Description ####

议会里有N个议员，每个议员有两个属性：级别和忠诚值。

现在你要在议会通过一个议案，一个议案通过当且仅当严格超过一半的议员投赞同票。一个议员投赞同票的几率就是忠诚值除以100。

议员们有着奇怪的癖好：他们都喜欢吃糖。你带了K个糖果用来贿赂议员，每个糖果的作用是使得某个议员的忠诚值增加10。贿赂要在投票开始前完成。（注意任意议员的忠诚值不可能大于100）

投票之后，如果议案没有通过，你就会很暴力地把投了反对票的所有议员暗杀掉。假设你要暗杀的议员集合是S，那么成功率就是A/(A+B)；其中A是给定的常数，B是S中所有议员级别的和。当暗杀成功后你的议案就会获得通过。

现在要求最优贿赂方案下最大的成功几率是多大。

#### Input ####

第一行三个整数N，K和A，意义如题目所述；

接下来N行每行两个整数ai，bi分别表示每个议员的级别和忠诚值。

#### Output ####

一个实数表示可能的最大成功几率。保留6位小数。

#### Sample Input ####

5 3 100
    11 80
    14 90
    23 70
    80 30
    153 70

#### Sample Output ####

0.962844

#### Data Constraint ####

#### Hint ####

对于40%的数据，保证N，K≤5

对于100%的数据，保证N，K≤9，A，ai≤9999，bi是10的倍数

# 分析 #

今日份水题

首先如果我们将每个人的忠诚值的都统计出来以后，我们可以暴力DFS用2^9的时间统计出其概率

然后我们发现统计忠诚值其实最大就9!的时间复杂度，而且因为有上限，肯定跑不满

所以两个DFS套在一起，时间复杂度O(能过)<O(9!\*2^9)

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    using namespace std;
    const int N=10;
    int n,k,A;
    int l[N],h[N];
    bool b[N];
    double ans;
    
    double DFS(int wch,int ok,int B) {
        if (wch==n+1) return (ok>n/2)?1.0:1.0*A/(A+B);
        return h[wch]/100.0*DFS(wch+1,ok+1,B)+(100.0-h[wch])/100.0*DFS(wch+1,ok,B+l[wch]);
    }
    
    void DFS(int wch,int candy) {
        if (wch==n+1||!candy) {
            ans=max(ans,DFS(1,0,0));
            return;
        }
        for (int i=0;i<=min((100-h[wch])/10,candy);i++) {
            h[wch]+=i*10;
            DFS(wch+1,candy-i);
            h[wch]-=i*10;
        }
    }
    
    int main() {
        scanf("%d%d%d",&n,&k,&A);
        for (int i=1;i<=n;i++) scanf("%d%d",&l[i],&h[i]);
        DFS(1,k);
        printf("%.6lf",ans);
    }

转载于:https://www.cnblogs.com/mastervan/p/10292184.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211215/49a61dca52c9469bbd2f487123fdd043.png

[DFS]JZOJ 2941 贿赂

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 [DFS]JZOJ 2941 贿赂