首页 > ACM题库 > HDU-杭电 > HDU 3203-Door Repairing-概率-[解题报告]HOJ
2014
03-06

HDU 3203-Door Repairing-概率-[解题报告]HOJ

Door Repairing

问题描述 :

Once upon a time, there was a famous university called Famous University. As thousands of students studied and lived in FU, a gigantic residential building was built, which is called ‘B37′. All students lived in B37 happily.

After decades, FU is still as famous as it had been in the past; however, the students living in it are now unhappy, because B37 is too old. Although the door of the building looks fine, it can be easily broken when being opened by some careless student too forcefully.

So, YY, the accommodation officer of B37, is facing an extremely serious problem.

With some mysterious methods, YY has predicted that exactly N students will enter or exit B37 during the next term. Unfortunately he doesn’t know who the careless ones are, so he assumes that every student opening the door has a probability of P percent to be a careless one. When the door is broken by some careless guy, YY may repair it immediately or after some time, with a cost of A yuan. Unfortunately when a student goes through the door and finds it already broken and not repaired, he will report it to the headmaster, and YY will be subject to a fine of B yuan. The door is in good condition before the term begins, and will be repaired by the university after the term ends, so YY can leave the door unrepaired at the end of the term.

Being good at mathematics, YY has made a strategy, to decide when to and when not to repair the door, in order to minimize his expense.

Please write a program to calculate the expectation of his expense.

输入:

The input consists of multiple test cases.

For each test case, there is one line containing four non-negative integers N, P, A, B described as above, with 0<=N<=100000, 0<=P<=100, 0<=A<=100, 0<=B<=100.

End of input is indicated by a line consisting of four zeros.

输出:

The input consists of multiple test cases.

For each test case, there is one line containing four non-negative integers N, P, A, B described as above, with 0<=N<=100000, 0<=P<=100, 0<=A<=100, 0<=B<=100.

End of input is indicated by a line consisting of four zeros.

样例输入:

10 100 0 1
10 100 1 0
2 50 2 1
0 0 0 0

样例输出:

0.0000
0.0000
0.5000
Hint
In the first sample, the door will be broken every time it is opened, but repairing is free, so just repair it every time. In the second sample, nothing will be fined, so just leave the door unrepaired. In the last sample, if the door is broken by the first student, YY will be fined 1 yuan, otherwise he doesn’t need to pay anything.

题目大意:

有一扇门, 一开始是好的, 一次来了n个人, 每个人有p的概率把门弄坏, 维修门的费用为a, 被一个人发现门坏的罚款为b, 求期望最小花费.

 

简要分析:

期望DP. 一开始想顺推没想出来, 后来被同学提醒开始想反推, 果然很顺利!

用f[i][0]表示第i个人来之前门坏, 到结束时的期望最小花费, f[i][1]则表示门好. 显然f[n][0] = min(a, b), f[n][1] = 0.0, 然后有

f[i][0] = min(f[i + 1][0] + b, a + p * f[i + 1][0] + (1.0 – p) * f[i + 1][1])

f[i][1] = min(f[i + 1][1] + a, p * f[i + 1][0] + (1.0 – p) * f[i + 1][1])

这样直接倒推即可, 最后f[1][1]就是答案.

 

代码实现:

#include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include <algorithm>
 using namespace std;
 
 const int MAX_N = 100000;
 int n, d, a, b;
 double p, f[MAX_N + 1][2];
 
 int main() {
     while (scanf("%d%d%d%d", &n, &d, &a, &b) != EOF) {
         if (!n && !d && !a && !b) break;
         p = d / 100.0;
         if (n <= 1) printf("%.4lf\n", 0.0);
         else {
             f[n][0] = min(a, b), f[n][1] = 0;
             for (int i = n - 1; i >= 1; i --) {
                 f[i][0] = min(f[i + 1][0] + b, a + p * f[i + 1][0] + (1.0 - p) * f[i + 1][1]);
                 f[i][1] = min(f[i + 1][1] + a, p * f[i + 1][0] + (1.0 - p) * f[i + 1][1]);
             }
             printf("%.4lf\n", f[1][1]);
         }
     }
     return 0;
 }


参考:http://www.cnblogs.com/zcwwzdjn/archive/2012/02/25/2367364.html