1260 Tickets http://acm.hdu.edu.cn/showproblem.php?pid=1260
有n个人排队买票，每个人需要的时间是a[i] (1=< i <=N)，但是现在可以两个人合买， 合买只能和前面一个人或者后面一个人合买，所用时间已知，求n个人都买完票所需要的最少时间
image.png
#include <stdio.h>
#include <string.h>
/**
* 考点：动态规划，从第一个人买票开始，
* 设前x人买票一共最少时间 = Sx
* 第x人单独买票时间 = Tx
* 第x人和第x+1人一起买票时间 = Hx
* 则x>=3时， Sx = min ( Sx-1+Tx, Sx-2+Hx-1 )
*/
int _1[2000]; //存储K个人单个买耗时
int _2[2000]; //存储K-1个两两一起买耗时
int _3[2000]; //最优方案 _3[i]存储代表，前i个人购买所需最小时间
int am = 1;
int min(int a, int b) { return a <= b ? a : b; }
void _printTime(int n) {
if (n < 10) {
printf("0");
}
printf("%d", n);
}
void printTime(int h, int m, int s) {
if (h >= 12) {
am = 0;
} else {
am = 1;
}
if (h > 12) {
h = h - 12;
}
_printTime(h);
printf(":");
_printTime(m);
printf(":");
_printTime(s);
if (am)
printf(" am\n");
else
printf(" pm\n");
}
int main() {
int cases;
scanf("%d", &cases);
while (cases--) {
int k;
scanf("%d", &k);
for (int i = 0; i < k; i++) {
scanf("%d", &_1[i]); //
}
for (int i = 0; i < k - 1; i++) {
scanf("%d", &_2[i]);
}
for (int i = 0; i < k; i++) {
if (i == 0) {
_3[i] = _1[i];
} else if (i == 1) {
_3[i] = min(_1[i] + _1[i - 1], _2[i - 1]);
} else {
_3[i] = min(_3[i - 1] + _1[i], _3[i - 2] + _2[i - 1]);
}
}
int s = _3[k-1], m = 0, h = 0;
while (s > 59) {
s -= 60;
m++;
}
while (m > 59) {
m -= 60;
h++;
}
printTime(h + 8, m, s);
}
}
3366 Passage http://acm.hdu.edu.cn/showproblem.php?pid=3366
一个人被困在一个城堡里，面前有n条路，他自己有m百万元，选择每一条路都有p概率通过，q概率遇到士兵，1-p-q概率道路不通；遇到士兵的话需要上交1百万，如果不够钱，则被杀死，问的是最优情况下多少概率可以成功逃脱
假设有 N 条出口，两两比较其中两条出口 A、B
先走哪个的优劣
A（P1，Q1） 设 P1/Q1 = K1
B（P2，Q2）设 P2/Q2 = K2
不花钱走出去的概率
先走A:
= P1+P2(1-P1-Q1)
= K1Q1 + K2Q2 - K2Q2K1Q1 - K2Q2Q1
先走B:
= P2+P1(1-P2-Q2)
= K2Q2 + K1Q1 - K2Q2K1Q1 - K1Q1Q2
结论 先走K越大不花钱概率越高
花1百万概率的概率
先走A
= Q1(1-Q2) + (1-Q1-P1)Q2
= Q1+Q2 - 2Q1Q2 -K1Q1Q2
先走B
= Q2(1-Q1) + (1-Q2-P2)Q1
= Q1+Q2-2Q1Q2 - K2Q1Q2
结论 先走K越大 花一百万的概率越低
花2百万概率的概率
= Q1*Q2
无论先走谁一样
对N条路分别两两比较，综上每次选择走 Pi / Qi 值最大的是最优解
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct way { //结构体way， p代表逃出去的概率，q代表有卫兵的概率
double p;
double q;
} W[1000];
double rate[1000][11]; //准备走i条路时有j百万的概率
int compare(const void *a, const void *b) {
struct way *aa = (struct way *)a, *bb = (struct way *)b;
if ((*aa).p / (*aa).q < (*bb).p / (*bb).q) {
return 1;
} else {
return -1;
}
}
int main() {
int T;
scanf("%d", &T);
int num = 0;
while (num++ < T) {
memset(W, 0, sizeof(W));
memset(rate, 0, sizeof(rate));
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%lf %lf", &W[i].p, &W[i].q);
}
qsort(W, n, sizeof(W[0]), compare);
double result = 0.0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= m; j++) {
if (0 == i) { //刚开始 在第一条路之前有m百万
if (j == m) {
rate[i][j] = 1.0;
result += rate[i][j] * W[i].p;
} else {
rate[i][j] = 0.0;
}
} else {
rate[i][j] = 0.0;
if (j + 1 <= m) {
rate[i][j] += rate[i - 1][j + 1] *
W[i - 1].q; //上一条路j+1百万消耗1百万
}
rate[i][j] +=
rate[i - 1][j] *
(1 - W[i - 1].p - W[i - 1].q); //上一条路j百万返回
result += rate[i][j] * W[i].p; //在此条路逃出成功
}
}
}
printf("Case %d: %.5lf\n", num, result);
}
}
End
