hdu2142题目链接 题意：有n个订单和可以在m小时内制作月饼 接下来是n个订单的信息:需要在mon月,d日,year年,h小时交付订单r个月饼 接下来一行t,s表示制作的月饼可以保质t天，每保质一天需要花费s的价值 接下来m行表示从第0小时开始在该时间制作月饼的花费的价值 求完成所有订单消耗的最小价值 思路：一开始毫无头绪。。因为读错题了。。。之后发现做月饼只能在整点做，即使是提前，也只能提前整数个小时做。 然后发现冰箱的容量是没有限制的，所以每个订单单独考虑即可。 那么对于每一个订单，我们要找到订单当天以及之前T天，这T+1天中做月饼花费最少的那天做月饼。 但是如果对于每个订单，如果每次都更新相应的价值，找一次最小值，复杂度会 …

poj 3368 题目链接 题意：给出n个非减的数a[i],求区间[l,r]中出现次数最多的数的出现的次数。 思路：由于数列非减，那么相等的数一定相邻。很容易系哪个到构造另一个数组f[i]，表示从当前位置向左边延伸最多延伸几个相等的数。 f[i] = f[i-1] + 1 (iff a[i]==a[i-1]) 然后查询的时候。 如果直接用ST算法查询rmq的话。。。 可能产生错误结果，原因是f[i]是从左边1到i这段连续区间里当前数出现的次数。 但是查询区间不一定是从1开始，所以查询区间内的第一段连续相等的数可能不完整。。。想了半天。。最后看了题解，发现是这部分暴力来搞。但是如果所有数列中所有数都相等，这样的复杂度就达到 …

poj2452题目链接 题意：给你一组数a[n]，求满足a[i] < a[k] < a[j] (i <= k <= j)的最大的j-i。 思路：大概能想到是rmq，然后想出了一个错误复杂度的错误思路，还直到对拍才发现== 转载一篇题解：poj2452解题报告 收获最大的是： 对于最大值和最小值返回val还是位置的转化竟然可以这样容易! 对于最大值和最小值返回val还是位置的转化竟然可以这样容易! 对于最大值和最小值返回val还是位置的转化竟然可以这样容易! 只要 int _min(int l,int r) { if (a[l]<a[r]) return l; return r; } 这样一个函数就可以 …

lightoj 1081 题目链接 题意：和上一道一样，但是由于size变成了500，如果按照之前的做法会tle + mle... 很容易发现，由于是方阵，长宽是相等的，所以有一维是可以省略的。 也就是所谓的降维？ /* *********************************************** Author :111qqz Created Time :2016年05月16日 星期一 19时24分26秒 File Name :code/loj/1081.cpp ************************************************ */ #include <cstdio> …

poj2019题目链接 题意：给一个方阵，k个查询，每个查询求某个方阵的最大值和最小值之差。 思路：二维rmq.同时用到最大值和最小值的话可以把初始化写在一起。 /* *********************************************** Author :111qqz Created Time :2016年05月16日 星期一 18时31分23秒 File Name :code/poj/2019.cpp ************************************************ */ #include <cstdio> #include <cstring> …

hdu2888题目链接 题意：问某个矩阵内的最大值，并且问最大值是否是在四个角中出现。 思路：二维rmq.需要注意数组稍微开大1就会MLE,因为是四维数组，一维大一点，整个就会大很多==。 /* *********************************************** Author :111qqz Created Time :2016年05月16日 星期一 16时51分00秒 File Name :code/hdu/2888.cpp ************************************************ */ #include <cstdio> #include …

1636: [Usaco2007 Jan]Balanced Lineup Time Limit: 5 Sec Memory Limit: 64 MB Submit: 680 Solved: 493 [Submit][Status][Discuss] Description For the daily milking, Farmer John's N cows (1 <= N <= 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of …