专栏首页owentPOJ 2192 Zipper HDU 2059 龟兔赛跑

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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 不知道是哪一年的腾讯马拉松题目 照片评级 解题报告

    结果就一不小心看到了这个充满回忆的ACM模式竞赛,还有咱腾讯的,就忍不住看了一下。

    owent
  • C/C++语言常用排序算法

    资料由互联网收集整理,供新手参考学习 这里又生动点的演示:http://www.cnblogs.com/wangfupeng1988/archive/2011...

    owent
  • POJ PKU 2596 Dice Stacking 解题报告

    题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=2596

    owent
  • LightOj_1079 Just another Robbery

      抢银行(这个背景最爱了), 有n家银行, 每家银行抢劫被抓的概率是p[i],你认为当你被抓的概率低于P的时候是安全的。

    若羽
  • LightOj_1030 Discovering Gold

      在一个1 X N 的格子上, 每个格子都有一定的黄金, 你从第一个格子出发, 问到最后一个格子得到黄金的期望。

    若羽
  • FZU 2098 刻苦的小芳(卡特兰数,动态规划)

    Problem 2098 刻苦的小芳 Accept: 42 Submit: 70 Time Limit: 1000 mSec Memory ...

    ShenduCC
  • P1060 开心的金明

    题目描述 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置...

    attack
  • 【HDU - 4341】Gold miner(分组背包)

    给出每个黄金的坐标、价值及耗时,同一方向的黄金只能依次取,求T时间内收获的最大值。

    饶文津
  • 动态规划 导弹拦截

    题意:一种导弹拦截系统的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有...

    Kindear
  • Golang Leetcode 377. Combination Sum IV.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89089210

    anakinsun

扫码关注云+社区

领取腾讯云代金券