盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 更新日志

hdu 5089 Revenge of iSea (数学 概率)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5089

题意

给出N道难度递增的题目,难度用可能做出的百分比表示,选出K道题目使得做出K-1道题目的概率最大。

思路

假设最优解已经包含了k-1个了,现在来选取最后一个。K-1个全部做出的概率是$P_a(k-1)$,有一道未做出的概率是$P_l(k−1)$,现在选取的是$P_k$,那么做出K-1道的概率是
$P_a(k−1){\times}(1−P_k)+P_l(k−1){\times}P_k=P_a(k−1)+P_k{\times}(P_l(k−1)−P_a(k−1))$
这是一个关于$P_k$的一次函数,如果$P_l(k−1)−P_a(k−1)$为正,选取最大的$P_k$,否则选取最小的。
这样,可以证明答案一定是选取两边的概率,枚举比较一下就可以算出最大的概率了。
还有最后一个问题,需要求字典序最小的。对于左边选取的$P_i$,当然index越小越好,对于右边的,如果存在相同的value,应该选取index较小的。比如90 80 30 30,如果答案是第一个和最后一个,为了取得最小的字典序,需要用第三个来替换一下第四个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF (1 << 30)
#define LINF (1LL << 60)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define eps 1e-8
#define debug puts("===============")
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)
typedef long long ll;
typedef unsigned long long ULL;
double p[50];
int vis[50];
int main () {
int t, n, k;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%lf", p + i);
p[i] /= 100;
}
memset(vis, 0, sizeof(vis));
int pos[50], cnt = 0, tot = 0;
double ans = 0;
for (int i = 0; i <= k; i++) {
cnt = 0;
for (int j = 0; j < i; j++) pos[cnt++] = j;
for (int j = 0; j < k - i; j++) pos[cnt++] = n - j - 1;
double res = 0;
for (int j = 0; j < cnt; j++) {
double tmp = 1;
for (int l = 0; l < cnt; l++) {
if (l != j) tmp *= p[pos[l]];
else tmp *= (1 - p[pos[l]]);
}
res += tmp;
}
//cout<<res<<endl;
if (res - ans > -eps) { //这里为-eps是为了保证选的为最小字典序
ans = res;
tot = i;
}
}
for (int i = 0; i < tot; i++) vis[i] = 1;
int now;
for (int i = n - (k - tot); i < n; i++) {
now = i;
for (int j = i; j >= 0; j--) {
if (vis[j] || p[j] > p[i]) break;
now = j;
}
vis[now] = 1;
}
for (int i = 0, j = 0; i < n; i++) {
if (vis[i]) {
j++;
printf("%d%c", i + 1, j == k ? '\n' : ' ');
}
}
}
return 0;
}

更新日志

  • 2014-11-4 AK