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 条评论
登录 后参与评论

相关文章

来自专栏Spark学习技巧

视频:JDBCRDD源码及自定义JDBCRDD的分区策略

, "SELECT id,aa FROM bbb where ? <= ID AND ID <= ?", lowerBound = 3, upperBound ...

1281
来自专栏码匠的流水账

springboot2的hikari数据库连接池默认配置

Spring-Boot-2.0.0-M1版本将默认的数据库连接池从tomcat jdbc pool改为了hikari,这里主要研究下hikari的默认配置

1K1
来自专栏闻道于事

JavaWeb 例子 JDBC+JSP登陆注册留言板

注册页面: <%@ page language="java" contentType="text/html; charset=UTF-8" pageEn...

4216
来自专栏成长道路

JDBC静态sql语句连接的工具类编写

为了方便静态SQL语句进行增删改查的操作,编写了一个工具类进行操作。 import java.sql.Connection; import java.sql....

2390
来自专栏IT开发技术与工作效率

VBA破解VBA密码

3275
来自专栏杨建荣的学习笔记

设计模式之工厂方法(r4笔记第89天)

设计模式中,工厂方法模式的使用还是很频繁的,但是似乎在工作中没有留意或者重视。 在各大网站中对于工厂方法模式的例子一般都是举女娲造人的例子,我就不做重复工作了,...

3637
来自专栏Hongten

Java Annotation(Java 注解)

如果你想知道java annotation是什么?你可以先看看:“http://www.infoq.com/articles/Annotation-Hammer...

1914
来自专栏文武兼修ing——机器学习与IC设计

移位相减除法器

移位相减除法器 基本算法 与使用移位相加实现加法一样,移位减法可以实现除法,基本算法如下描述 将除数向左移位直到比被除数大 使用移位后的除数与被除数比较,若除数...

55710
来自专栏海说

Java应用中常见的JDBC连接字符串(SQLite、MySQL、Oracle、Sybase、SQLServer、DB2)

Java应用中常见的JDBC连接字符串 Java应用中连接数据库是不可或缺的,于是便整理一些可能用到的JDBC的jar包及其相匹配的URL,以备日后查阅。 1)...

3980
来自专栏一枝花算不算浪漫

[JavaWeb]关于DBUtils中QueryRunner的一些解读.

6686

扫码关注云+社区

领取腾讯云代金券