题解 P3849 【[TJOI2007]足彩投注】

Anita_Hailey · 2019-12-15 21:00:13 · 题解

足彩投注

题目概述

题目背景

了解足球彩票的人可能知道，足球彩票中有一种游戏叫做“胜负彩”，意为猜比赛的胜负。下面是一些与胜负彩有关的术语

注 ：每一组有效组合数据。

投 注：彩民以现金购买足球彩票的行为。

单式投注：彩民对于所有球队的比赛成绩均只选择一种预测结果的投注方式。投注的数量（注数）为1。

复式投注：彩民对于某些场次的比赛成绩选择两种以上的预测结果的投注方式。投注的数量为复式投注的组合数。例如，某彩民对一场比赛预测了两个结果（例如，胜平）， 另一场比赛预测了三个结果（胜负平），其他比赛都只预测了一种结果，那么注数就是2×3 = 6。这样的一个复式投注，可以看成一个包含六种单式投注的集合。

胜负彩的玩法一般是这样的。彩票机构指定一轮比赛中的若干场，让彩民去猜每场比赛的结果（胜、负、平）。根据彩民猜中比赛的场次，来确定中奖的额度。

题目描述

我们现在考虑一个简化的模型。对于一轮比赛，彩民需要竞猜其中n场比赛的结果，每场比赛的胜负平都有一个概率p(i, r)。其中，i表示第i场比赛,r = 0, 1, 2，分别表示比赛结果的（主队）负、平、胜。p(i, r)则表示第i场比赛、结果为r的概率。此外，还有一个概率q(i, r)，表示第i场比赛，投注购买结果为r的概率。

例如，如果q(1,0)=0.5，我们可以知道第一场比赛有50%的投注会买主队输球。我们假设这n场比赛互不相关，即p(i, r)的结果不会受p(j, r’)的影响，q(i, r)的结果也不会受q(j, r’)的影响(r ≠ r’)。

在这个模型里，我们规定，必须猜中全部n场比赛的结果才能获奖。总奖金为M，由所有获奖的投注平分。因此，对于一个单式投注Ri = \{r_{i1}, r_{i2}, …, r{in}\}，rij表示投注Ri对第j场比赛的预测结果，它的中奖概率为

设投注总数为N，那么中奖的投注总数为：

于是，投注Ri所能得到的奖金的期望（平均意义下能够获得的奖金数）就是：

复式投注R中，只要有一个Ri猜对所有比赛结果，即可中奖。因此，复式投注R所能获得的奖金的期望就是：

我们的问题是，给定n场比赛的信息（胜负平的概率和彩民购买三种结果的概率），以及复式投注中可以购买的最大注数U，要求设计一种复式投注的方案，在不超过最大注数（复式投注的注数k ≤ U）的前提下，使得获得奖金的期望最大。

输入格式

第一行四个整数n, N, M, U（n, U ≤ 10^4, N, M ≤ 10^9）。

以下n行，每行六个实数。第i + 1行的六个实数为p(i, 0), p(i, 1), p(i, 2), q(i, 0), q(i, 1),q(i, 2)，用来描述第i场比赛的相关信息。其中，p(i, 0) + p(i, 1) + p(i, 2) = 1, q(i, 0) + q(i, 1) + q(i, 2) = 1, q(i, j) ≠ 0。

输出格式

一个实数，表示最大的奖金期望的自然对数

输出保留3位小数（四舍五入）。

simple.in

1 10 10 1
0.3 0.2 0.5 0.7 0.2 0.1

simple.out

1.609

问题分析

样例分析

说实话，刚看到题时，我蒙了，这怎么多数学公式怎么搞。所以推明白了样例，就大概明白了

拿出我的Casio，e^{1.609}=4.9978,那么没有求对数时就是5，在乘上N除以M就知道\frac {P(R_i)} {Q(R_i)}是5通过细致细致入微的关差，刚好0.5/0.1=5。

注意p是结果的概率，q是投注的概率

我们看到U=1,则最大注数是1,也就是说都是单注，那事实上在这个样例，我们就要求一个Max_{0<=i<=2}\{\frac{p(1,i)}{q(1,i)} \},那么这个样例分析，U=1时看不出来什么有什么的，我们把U=2，再来看这个样例，我们可以把复式投注看成是两个单注，投注赢的奖金是0.3/0.7=0.428，而投注平的奖金为0.2/0.2=1，投注输的奖金为0.5/0.1=5（这怕不是国足）

这时我们的两个注要压平和输。

在U=3时我们三个注都压。那么对于，一场比赛我们的押注方式共有7种，可事实上，我们只用考虑其中的三种情况，因为由于贪心的思想在注数一定时，我们选择概率奖金数最大(即\sum_{e=1}^k\frac{p(i,j)}{q(i,j)})的。

于是我们真的懂了这个又臭又长的答案式子，先不考虑ln

其中a(i,k_i),表示我第i场比赛投k_i个注的期望的最大奖金概率就是好几个\frac{p(i,j)}{q(i,j)}

引理

ln(ab)=ln(a)+ln(b,证明吗，幂运算，送的。

考虑到小数乘法的精度损失——其实挺重要的

我们不妨对式子先取ln，成为加法，又快有准

于是式子两边同时取ln有

我们就有了以下代码来生成a

for(int i=1;i<=n;i++){
        scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f);
        tmp[0]=a/d;
        tmp[1]=b/e;
        tmp[2]=c/f;
        cha[i][1]=log(max(tmp[1],max(tmp[0],tmp[2])));
        cha[i][2]=log(max(tmp[1]+tmp[0],max(tmp[1]+tmp[2],tmp[0]+tmp[2])));
        cha[i][3]=log(tmp[1]+tmp[0]+tmp[2]);
    }

算法分析

题目是问我们一个最大的期望答案,又不输出方案，那我就是dp

考虑他的状态f(i,j),，表示在已经押注了i场比赛，还剩j个注是期望奖金概率的最大值取ln，这里我们用了log_e(i)函数的单增性，这是一个不完全重复背包

我们的所求即为f(n,U)，再来考虑我们的转移方程

注意这里的j一定不能为0因为注数为零时后面投不下去了

我们要注意的是这个t题的数据有些大，如果开二维的话要10G左右qwq，在计算f(i,j),是我们只用到了f(i-1，j/k)的数据那么我们可以加上一维数组优化，注意递推是要倒序求（完全的要顺序）。

for(int i=1;i<=n;i++)
        for(int j=U;j>=1;j--)
            for(int k=1;k<=3;k++)
                if(j/k>=1)
                    data[j]=max(data[j],data[j/k]+cha[i][k]);

于是我就很愉快的卡过了这道题

接下来是完整代码

#include <bits/stdc++.h>
using namespace std;
const int Maxn=10001,MaxU=10001;
double a,b,c,d,e,f,data[MaxU],cha[Maxn][4],tmp[3];;
int n,M,N,U;
int main(){
    scanf("%d%d%d%d",&n,&N,&M,&U);
    for(int i=1;i<=n;i++){
        scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f);
        tmp[0]=a/d;
        tmp[1]=b/e;
        tmp[2]=c/f;
        cha[i][1]=log(max(tmp[1],max(tmp[0],tmp[2])));
        cha[i][2]=log(max(tmp[1]+tmp[0],max(tmp[1]+tmp[2],tmp[0]+tmp[2])));
        cha[i][3]=log(tmp[1]+tmp[0]+tmp[2]);
    }
    for(int i=1;i<=n;i++)
        for(int j=U;j>=1;j--)
            for(int k=1;k<=3;k++)
                if(j/k>=1)
                    data[j]=max(data[j],data[j/k]+cha[i][k]);
    printf("%.3lf",log(M)-log(N)+data[U]);
    return 0;
}

很短，只有24行，这又一次说明了推样例的重要性

回头望月

当我再看我的dp是有些伤感，我是怎么堆出dp转移方程的？每一场比赛，你必须投注，那么，在dp过程中万一一次dp的之不改变即cha<0，怎么办，我是错了吗。

事实上，在思考之后这个问题等价于a+b+c=1,d+e+f=1

问在\frac{a}{d},\frac{b}{e},\frac{c}{f}中有最大的一个，两个，三个求和，和是否大于1。

其实是显然的，考虑和谐的情况三个都是1，显然的吗，哈哈