POJ 2192 Zipper HDU 2059 龟兔赛跑

今天心情好，刷了两到ACM水题，思路很简单都在注释里，所以直接贴代码:

/**
 * @file 龟兔赛跑.cpp
 * @brief 龟兔赛跑 AC代码 (DP)
 * DP方程式: [到第i的充电站的最短时间] = [到最后一个冲了电的充电站的最短时间] + [那个充电站到第i个充电站的时间]
 *
 * @link http://acm.hdu.edu.cn/showproblem.php?pid=2059
 * @version 1.0
 * @author OWenT
 * @date 2013.07.15
 *
 * @history
 *
 *
 */

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <numeric>

int pn[128];
double dp[128]; /** dp[i] 表示 到第i个充电站的最小时间(0为开始位置，n+1为终点) **/

double calc_charge_time(int dis, int v1, int v2, int c) {
    if (dis <= c)
        return 1.0 * dis / v1;

    return 1.0 * c / v1 + 1.0 * (dis - c) / v2;
}

int main(int argc, char* argv[]) {
    using namespace std;

    double eps = std::numeric_limits<double>::epsilon();
    int l, n, c, t, vr, v1, v2;

    while(cin>> l) {
        cin >> n>> c>> t>> vr>> v1>> v2;

        pn[0] = 0; /** 0为起点 **/
        for (int i = 1; i <= n; ++ i) {
            cin>> pn[i];
        }
        pn[n + 1] = l; /** n+1为终点 **/

        memset(dp, 0, sizeof(dp));
        for(int i = 0; i <= n + 1; ++ i) {
            dp[i] = calc_charge_time(pn[i] - pn[0], v1, v2, c);
        }

        for(int i = 1; i <= n + 1; ++ i) {
            for(int j = 0; j < i; ++ j) {
                double tc = calc_charge_time(pn[i] - pn[j], v1, v2, c) + t + dp[j];
                dp[i] = std::min(tc, dp[i]);
            }

        }

        double rt = 1.0 * l / vr, tt = dp[n + 1];

        if (tt < rt)
            puts("What a pity rabbit!");
        else
            puts("Good job,rabbit!");
    }

    return 0;
}

/**
 * @file Zipper.cpp
 * @brief Zipper AC代码 (DP)
 * @link http://poj.org/problem?id=2192
 * DP方程式: [A串消耗个数i][B串消耗个数j] = min{[A串消耗个数i - 1][B串消耗个数j]|[A串消耗个数i][B串消耗个数j + 1]}
 * 以上分支选取条件是 A或B的新选用字符和C串新字符匹配
 *
 * @version 1.0
 * @author OWenT
 * @date 2013.07.15
 *
 * @history
 *
 *
 */

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <numeric>


char strA[256], strB[256], strC[512];
int dp[256][256]; /** dp[i][j] = k 表示A消耗了i个字符，B消耗了j个字符，拼成的C串消耗了k个字符（其实就是i+j） **/

int main(int argc, char* argv[]) {
    using namespace std;
    int s, n;

    scanf("%d", &n);
    for( s = 0; s < n; ++ s) {
        scanf("%s %s %s", strA, strB, strC);
        int lenA = strlen(strA);
        int lenB = strlen(strB);
        int lenC = strlen(strC);
        bool bFlag = false;

        if ( lenC != lenA + lenB ) {
            printf("Data set %d: no\n", s + 1);
            continue;
        }

        memset(dp, 0, sizeof(dp));

        if (strA[0] == strC[0])
            dp[1][0] = 1;
        if (strB[0] == strC[0])
            dp[0][1] = 1;

        for (int i = 0; i <= lenA; ++ i) {
            for (int j = 0; j <= lenB; ++ j) {
                if (0 == dp[i][j])
                    continue;

                int ri = i + 1, rj = j + 1;

                if (strA[i] == strC[dp[i][j]]) {
                    dp[ri][j] = dp[i][j] + 1;
                    if (ri + j == lenC)
                        bFlag = true;
                }

                if (strB[j] == strC[dp[i][j]]) {
                    dp[i][rj] = dp[i][j] + 1;
                    if (i + rj == lenC)
                        bFlag = true;
                }
            }
        }

        printf("Data set %d: %s\n", s + 1, bFlag? "yes": "no");
    }

    return 0;
}