【HDOJ】4122 Alice's mooncake shop

摘要:
RMQ的基本和简单问题。

RMQ的基础题目,简单题。

  1 /* 4122 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <algorithm>
 12 #include <cstdio>
 13 #include <cmath>
 14 #include <ctime>
 15 #include <cstring>
 16 #include <climits>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <functional>
 20 #include <iterator>
 21 #include <iomanip>
 22 using namespace std;
 23 //#pragma comment(linker,"/STACK:102400000,1024000")
 24 
 25 #define sti                set<int>
 26 #define stpii            set<pair<int, int> >
 27 #define mpii            map<int,int>
 28 #define vi                vector<int>
 29 #define pii                pair<int,int>
 30 #define vpii            vector<pair<int,int> >
 31 #define rep(i, a, n)     for (int i=a;i<n;++i)
 32 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 33 #define clr                clear
 34 #define pb                 push_back
 35 #define mp                 make_pair
 36 #define fir                first
 37 #define sec                second
 38 #define all(x)             (x).begin(),(x).end()
 39 #define SZ(x)             ((int)(x).size())
 40 #define lson            l, mid, rt<<1
 41 #define rson            mid+1, r, rt<<1|1
 42 
 43 const int maxm = 1e5+5;
 44 const int maxn = 2505;
 45 int T[maxn], N[maxn];
 46 int cost[maxm], val[maxm];
 47 int dp[maxm][17];
 48 int days[12] = {
 49     31, 28, 31, 30, 31, 30, 
 50     31, 31, 30, 31, 30, 31
 51 };
 52 int days_[12] = {
 53     31, 29, 31, 30, 31, 30, 
 54     31, 31, 30, 31, 30, 31
 55 };
 56 char month[12][4] = {
 57     "Jan", "Feb", "Mar", "Apr", 
 58     "May", "Jun", "Jul", "Aug", 
 59     "Sep", "Oct", "Nov", "Dec"
 60 };
 61 char s[12];
 62 int yy, mm, dd, hh;
 63 int n, m;
 64 
 65 int getMon(char *s) {
 66     rep(i, 0, 12)
 67         if (strcmp(month[i], s) == 0)
 68             return i;
 69         
 70     return -1;
 71 }
 72 
 73 bool isLeapYear(int y) {
 74     return y%400==0 || (y%100!=0 && y%4==0);
 75 }
 76 
 77 int getTime() {
 78     mm = getMon(s);
 79     int ret = 0;
 80     
 81     rep(i, 2000, yy) {
 82         if (isLeapYear(i))
 83             ret += 366;
 84         else
 85             ret += 365;
 86     }
 87     if (isLeapYear(yy)) {
 88         rep(i, 0, mm)
 89             ret += days_[i];
 90     } else {
 91         rep(i, 0, mm)
 92             ret += days[i];
 93     }
 94     ret += dd-1;
 95     ret *= 24;
 96     ret += hh + 1;
 97     
 98     return ret;
 99 }
100 
101 void init_RMQ() {
102     int i, j;
103     
104     for (i=0; i<m; ++i)
105         dp[i][0] = i;
106         
107     for (j=1; (1<<j)<=m; ++j) {
108         for (i=0; i+(1<<j)-1<m; ++i) {
109             if (val[dp[i][j-1]] < val[dp[i+(1<<(j-1))][j-1]])
110                 dp[i][j] = dp[i][j-1];
111             else
112                 dp[i][j] = dp[i+(1<<(j-1))][j-1];
113         }
114     }
115 }
116 
117 int RMQ(int l, int r) {
118     if (l < 0)
119         l = 0;
120     
121     int k = 0;
122     
123     while (1<<(k+1) <= r-l+1)
124         ++k;
125     
126     if (val[dp[l][k]] < val[dp[r-(1<<k)+1][k]])
127         return dp[l][k];
128     else
129         return dp[r-(1<<k)+1][k];
130 }
131 
132 int main() {
133     ios::sync_with_stdio(false);
134     #ifndef ONLINE_JUDGE
135         freopen("data.in", "r", stdin);
136         freopen("data.out", "w", stdout);
137     #endif
138     
139     int st, cst;
140     int idx, tmp;
141     __int64 ans;
142     
143     while (scanf("%d%d", &n, &m)!=EOF && (n||m)) {
144         rep(i, 0, n) {            
145             scanf("%s%d%d%d%d", s, &dd, &yy, &hh, &N[i]);
146             T[i] = getTime();
147         }
148         scanf("%d%d", &st, &cst);
149         rep(i, 0, m) {
150             scanf("%d", &cost[i]);
151             val[i] = cost[i] + cst * (m - i);
152         }
153         
154         ans = 0;
155         init_RMQ();
156         rep(i, 0, n) {
157             idx = RMQ(T[i]-st, T[i]-1);
158             tmp = cost[idx] + (T[i]-1-idx) * cst;
159             ans += 1LL * tmp * N[i];
160         }
161         
162         printf("%I64d
", ans);
163     }
164     
165     #ifndef ONLINE_JUDGE
166         printf("time = %d.
", (int)clock());
167     #endif
168     
169     return 0;
170 }

免责声明:文章转载自《【HDOJ】4122 Alice's mooncake shop》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇【HDOJ】4370 0 or 1【HDOJ】4393 Throw nails下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

Nokia是否还有未来 小议诺基亚和微软的战略布局

昨天和别人聊天谈到手机行业的现状,感触颇多也受到一定启发,所以想在此一点点记录自己对这个行业发展的一些看法,因为并非专门研究,因此必然会有不少瑕疵,还望海涵并指正。 首先谈到的就是Nokia,从一个霸主在短短5年不到的时间落魄成现在的状况,已经成为大家茶余饭后的谈资。Nokia的救赎之路难免坎坷,也正因为如 此,看到很多网友发出Nokia已死的言论,事实上我...

London2012同步时间新语

#!/usr/bin/env python#encoding="utf-8""""free use navicat & sqlyog"""import datetimefrom dateutil import parserif __name__=="__main__":import sys,osif len(sys.argv)>1:import...

PhpStorm terminal无法输入命令的解决方法

下面小编就为大家带来一篇PhpStorm terminal无法输入命令的解决方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧 在使用PhpStorm时,点击下面的terminal时,发现怎么输入都不显示,于是一查才发现是phpstorm与win10系统不兼容的问题,只要设置一...

CactiEZ中文版10.1正式发布

CactiEZ 中文版 CactiEZ中文版10.1正式发布 文章分类: 安装手册 作者: ivory — 30 条评论 2011 年 07 月 13 日 CactiEZ中文版是最简单有效的Cacti中文解决方案,整合Spine,RRDTool和美化字体。集成Thold,Monitor,Syslog,Weathermap,Realtime,Er...

use java style regular expression in groovy fetch and extractor info ,fucking urgly

import java.util.regex.Matcher;import java.util.regex.Pattern;import java.util.regex.PatternSyntaxException;System.properties.putAll( ["http.proxyHost":"10.10.224.97", "http.proxyP...

北京个人ADSL和企业ADSL有什么区别啊?

北京个人ADSL和企业ADSL有什么区别啊?_百度知道北京个人ADSL和企业ADSL有什么区别啊?2006-9-11 11:05提问者:ykul| 浏览次数:2107次都是1M的个人150包月,企业600包月,想知道有什么区别,价钱差的有点多了,我要是企业的装个人的1M可行吗?我来帮他解答2006-9-11 11:13满意回答一样的东西,就和电话一样,企业电...