动态规划 1260 Tickets

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