Articles tagged as

  1. [POJ1771] Elevator Stopping Plan

    Description

    ZSoft Corp. is a software company in GaoKe Hall. And the workers in the hall are very hard-working. But the elevator in that hall always drives them crazy. Why? Because there is only one elevator in GaoKe Hall, while there are hundreds of companies in it. Every morning, people must waste a lot of time waiting for the elevator.

    Hal, a smart guy in ZSoft, wants to change this situation. He wants to find a way to make the elevator work more effectively. But it’s not an easy job.

    There are 31 floors in GaoKe Hall. It takes 4 seconds for the elevator to raise one floor. It means:

    It costs (31-1)*4=120 seconds if the elevator goes from the 1st floor to the 31st floor without stop. And the elevator stops 10 second once. So, if the elevator stops at each floor, it will cost 30*4+29*10 = 410 seconds (It is not necessary to calculate the stopping time at 31st floor). In another way, it takes 20 seconds for the workers to go up or down one floor. It takes 30*20 = 600 seconds for them to walk from the 1st floor to the ...

  2. [NOIP05] 过河

    描述

    在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中L是桥的长度)。坐标为0的点表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数(包括S,T)。当青蛙跳到或跳过坐标为L的点时,就算青蛙已经跳出了独木桥。

    题目给出独木桥的长度L,青蛙跳跃的距离范围S,T,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。

    输入格式

    输入文件river.in的第一行有一个正整数L(1 <= L <=10^9),表示独木桥的长度。第二行有三个正整数S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数,其中1 <= S <= T <= 10,1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。所有相邻的整数之间用一个空格隔开。

    输出格式

    输出文件river.out只包括一个整数,表示青蛙过河最少需要踩到的石子数。

    数据规模

    对于30%的数据,L <= 10000;

    对于全部的数据,L <= 10^9。

    题解

    一看题,这无后效性和最优子结构也太明显了,随手就可以列出转移方程。令dp[i]表示处于i位置时,最少还要踩到几个石子(包括当前点)才能到达对岸。bridge[i]为点i处的石子个数(0或1)。则

    当0≤i<L时:dp[i] = min{dp[i+j]} + bridge[i] (S≤j≤T)

    当i≥L时:dp[i]=0

    问题的解即为dp[0]。

    但是这样写完交上去最多只能得30分。直接硬搞,复杂度是O(L*(T-S))的,T-S最大为9,无关紧要,但是L的最大值则是令人发指的10^9(青蛙跳这么长距离不累死么 – -),不TLE……恐怕需要10年以后的CPU了。那怎么办呢?(思考过程也许比较繁琐,要结论请直接看倒数第5段)

    数据范围往往是算法选择的最重要的提示。我们看到虽然L这么巨大,但是石子的总数却不超过100个。这说明什么?说明桥上必然有大段大段的无石子区间,而无石子区间的最大长度在极限情况下将接近10^9。即在跳跃中,青蛙经常会很郁闷地在巨长的无石子区间上跳啊跳啊,想踩个石子都踩不到。上面那个普通dp肯定会导致空白区间上大量的无必要决策而无谓耗费大量时间。要减少这种时间浪费,我们可以试图把大段的无石子区间等效转化为较短的无石子区间,从而使时间开销降至可承受范围。

    首先考虑最简单的情况:S=T。这种情况下,这个诡异的青蛙只能跳固定的长度。而跳的起点是0位置,那么青蛙经过的就只有S(或者说T,一回事)的整数倍点。如果石子的位置为S的整数倍,那么青蛙就一定会踩到,否则一定踩不到。比如S=T=3,L=100,那么青蛙经过的点就为且仅为0,3,6,…,96,99。在21、27、33、66等处的石子就一定能踩到,而20、40、80、92等处的石子就踩不到。于是,当S=T时,我们只需要数位置为S整数倍的石子有几个就得到了答案,不需要进行上面说到的“等效转化”。

    那如果S≠T呢?我们也从一个最简单的例子看起。假如S=5,T=6,青蛙从0位置开始跳,那么它可能到达的点是:

    5,6,

    10,11,12,

    15,16,17,18,

    20,21,22,23,24,

    25,26,27,28,29,30,31,32 ...

  3. [VIJOS 1037] 搭建双塔

    描述

    2001年9月11日,一场突发的灾难将纽约世界贸易中心大厦夷为平地,Mr. F曾亲眼目睹了这次灾难。为了纪念“9?11”事件,Mr. F决定自己用水晶来搭建一座双塔。

    Mr. F有N块水晶,每块水晶有一个高度,他想用这N块水晶搭建两座有同样高度的塔,使他们成为一座双塔,Mr. F可以从这N块水晶中任取M(1≤M≤N)块来搭建。但是他不知道能否使两座塔有同样的高度,也不知道如果能搭建成一座双塔,这座双塔的最大高度是多少。所以他来请你帮忙。

    给定水晶的数量N(1≤N≤100)和每块水晶的高度Hi(N块水晶高度的总和不超过2000),你的任务是判断Mr. F能否用这些水晶搭建成一座双塔(两座塔有同样的高度),如果能,则输出所能搭建的双塔的最大高度,否则输出“Impossible”。

    输入格式

    输入的第一行为一个数N,表示水晶的数量。第二行为N个数,第i个数表示第i个水晶的高度。

    输出格式

    输出仅包含一行,如果能搭成一座双塔,则输出双塔的最大高度,否则输出一个字符串“Impossible”。

    题解

    应该说是很简单的dp,但是我没有独立完成……说明我果然是巨菜啊……

    状态表示是我没见过的-_-。。。看了下别人的状态表示,然后就很容易地写出了方程。

    dp(i,j)表示用前i块水晶堆2个塔,两塔间高度差为j时,较低塔的最大高度。

    \begin{equation*} dp(i,j)=\max\{dp(i-1,j+h[i]), dp(i-1,j-h[i])+h[i], dp(i-1,h[i]-j)+j, dp(i-1,j)\} \end{equation*}

    注意处理边界……我还因为边界问题WA了一次,sigh……

    #include <fstream>
    #include <iostream>
    #include <climits>
    #include <cassert>
    using namespace std;
    int N,H[101],dp[101][2001];
    bool flag[101][2001];
    int memo(int i,int j){
        if(j<0) return INT_MIN;
        if(i==0&&j==0)  return 0;
        if(i==0)    return INT_MIN;
        assert(i<=N&&j<=2000);
        if(flag[i][j])  return dp[i][j];
        int ans=INT_MIN;
        if(ans<memo(i-1,j)) ans=memo(i-1,j);//do not put
        if(ans<memo(i-1,j+H[i]))    ans=memo(i-1,j+H[i]);//put on the higher
        if(ans<memo(i-1,j-H[i])+H[i ...
  4. [VIJOS 1014] 旅行商简化版

    背景

    欧几里德旅行商(Euclidean Traveling Salesman)问题也就是货郎担问题一直是困扰全世界数学家、计算机学家的著名问题。现有的算法都没有办法在确定型机器上在多项式时间内求出最优解,但是有办法在多项式时间内求出一个较优解。

    为了简化问题,而且保证能在多项式时间内求出最优解,J.L.Bentley提出了一种叫做bitonic tour的哈密尔顿环游。它的要求是任意两点(a,b)之间的相互到达的代价dist(a,b)=dist(b,a)且任意两点之间可以相互到达,并且环游的路线只能是从最西端单向到最东端,再单项返回最西端,并且是一个哈密尔顿回路。

    描述

    著名的NPC难题的简化版本

    现在笛卡尔平面上有n(n<=1000)个点,每个点的坐标为(x,y)(-2^31 < x,y < 2^31 ,且为整数),任意两点之间相互到达的代价为这两点的欧几里德距离,现要你编程求出最短bitonic tour。

    输入格式

    第一行一个整数n

    接下来n行,每行两个整数x,y,表示某个点的坐标。

    输入中保证没有重复的两点,保证最西端和最东端都只有一个点。

    输出格式

    一行,即最短回路的长度,保留2位小数。

    来源

    《算法导论(第二版)》 15-1

    题解

    基本DP

    这题需要补充一个条件:任何两点的x坐标都不相等。

    首先按照x坐标对所有点进行排序,并从西到东依次编号。这样我们就可以进行DP了。阶段可以按照从西到东的各个点来划分。

    image0

    如图,我们对E点代表的阶段进行决策,有两种决策:E连B或E连D。这样,类似B、D的两个点就可以表示一种状态。

    我们用dp[i][j]表示一种状态,表示在这两个点代表的状态之后,还能得到的最小长度。则有

    dp[i][j]=dp[j][i]=min{dp[i][k]+dist[j][k],dp[k][j]+dist[i][k]},其中(k=max(i,j)+1)

    dp[0][0]就是所求的解。边界也很好处理。时间复杂度为 O( N^2 )。

    源码:

    #include <iostream>
    #include <iomanip>
    #include <cstdlib>
    #include <cmath>
    using namespace std;
    double dp[1000][1000],dist[1000][1000];
    int N;
    struct Dot{ long x,y;}dots[1000];
    int cmp(const void *a, const void *b){
        return ((Dot*)a)->x-((Dot*)b)->x;
    }
    double memo(int a, int b){
        if(dp[a][b]>0)  return dp[a][b];
        if(a==N-1)  return dist[N-1][b];
        if(b==N-1)  return dist[N-1][a ...
  5. [URAL1183] Brackets sequence

    Let us define a regular brackets sequence in the following way:

    Empty sequence is a regular sequence. If S is a regular sequence, then (S) and [S] are both regular sequences. If A and B are regular sequences, then AB is a regular sequence. For example, all of the following sequences of characters are regular brackets sequences: :

    (), [], (()), ([]), ()[], ()[()]
    

    And all of the following character sequences are not: :

    (, [, ), )(, ([)], ([(]
    

    Some sequence of characters ‘(‘, ‘)’, ‘[‘, and ‘]‘ is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1a2…an is called a subsequence of the string b1b2…bm, if there exist such indices 1 ≤ i1 < i2 < … < in ≤ m, that aj=bij for all 1 ≤ j ≤ n.

    Input

    The input file contains at most 100 brackets (characters ‘(‘, ‘)’, ‘[‘ and ‘]‘) that are situated on a single line without any other characters among them.

    Output

    Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.

    Solution

    终于过了这题……WA了两次。第一次是判断括号匹配的栈写错了,WA#9;第二次是没有考虑输入文件是空串的情况,WA#13并持续一周 -_-|||

    而且这次也写垃圾了,长达80多行。好像原来的ural的内存限制是1000K?这样说我开一个100*100的string数组真是件奢侈的事情呢……

    #include <iostream>
    #include <fstream>
    #include <string>
    #include ...

Page 1 / 2