JZOJ 1772 - Holiday


https://www.codetd.com/article/2798845
经过几个月辛勤的工作,FJ决定让奶牛放假。假期可以在1…N天内任意选择一段(需要连续),每一天都有一个享受指数W。但是奶牛的要求非常苛刻,假期不能短于P天,否则奶牛不能得到足够的休息;假期也不能超过Q天,否则奶牛会玩的腻烦。FJ想知道奶牛们能获得的最大享受指数。
Input
第一行:N,P,Q.
第二行:N个数字,中间用一个空格隔开,每个数都在longint范围内。
Output
一个整数,奶牛们能获得的最大享受指数。
Sample Input
5 2 4
-9 -4 -3 8 -6
Sample Output
5
Data Constraint
50% 1≤N≤10000
100% 1≤N≤100000
1<=p<=q<=n
Hint
选择第3-4天,享受指数为-3+8=5。
看到区间的问题首先肯定是想到求前缀和,我们把[1,k]的和记为sum[k],可以得到sum[i] = sum[i - 1] + a[i],[l,r]的和即为sum[r] - sum[l - 1](这里视sum[0] = 0)。我们假设选择的区间为[l,r]且r固定,可知r−q+1≤l≤r−p+1r−q+1≤l≤r−p+1,若要使[l,r]区间的值最大,则sum[l - 1]需最小,才可使得sum[r] - sum[l - 1]最小,当i右移一位到i+1,因为p,q为给定不变的值,对应寻找最小sum[l-1]的区间也右移一位,与上题同。
如下图,当p=3,q=5时:
这里写图片描述
关于单调队列的运用还有很多,例如斜率优化DP等等。总而言之,使用单调队列优化DP,那么必会有求i之前某个范围的极值的操作,这类DP的方程通常为:
F[i]=min(F[j]+a[i]:j<i)F[i]=min(F[j]+a[i]:j<i)
a[i]是与j无关的数。
int n,p,q,l,r,head = 1,tail = 0,ans = -2147483647;
int que[100001],a[100001];
long long sum[100001];

int max(long long a,long long b)
{
    return a > b ? a : b;
}

int main()
{
    sum[0] = 0;
    scanf("%d %d %d", &n, &p, &q);
    for (int i = 1;i <= n;i++)
    {
        scanf("%d", &a[i]);
        sum[i] = sum[i-1] + a[i]; //记前缀和
    }
    for (r = p;r <= n;r++)
    {
        while (head <= tail && sum[que[tail]-1] >= sum[r-p]) tail--; //更优的sum[l - 1]予以插队
        que[++tail] = r+1-p; //入队
        while (head <= tail && que[head] < r+1-q) head++; //不处于维护范围内的出队
        ans = max(ans, sum[r]-sum[que[head]-1]); //更新答案
    }
    printf("%d\n", ans);
    return 0;
}

        前缀和 + dp + 单调队列。

        写了树状数组。。。。但是树状数组求区间和比前缀和要慢啊。。。

        首先前缀和,sum[i] = sum[i - 1] + sum[i – 2];所以对于区间[i,j],区间和sum(i,j) = sum[j] – sum[i],其中j – q <= i <= j – p;这时可以发现,若要sum(i,j)尽量大,那么=sum[i]要尽量小,这时要用单调递增队列维护i的区间,队列中存sum数组的下标。

        单调队列满足两个性质:

            1.单调队列必须满足从队头到队尾的严格单调性。

            2.排在队列前面的比排在队列后面的要先进队。

        元素进队列的过程对于单调递增队列,对于一个元素a 如果 a > 队尾元素,那么直接将a扔进队列;如果 a <= 队尾元素 则将队尾元素出队列,直到满足 a 大于队尾元素即可。

        枚举j从p到n,即枚举右端点,对于每个枚举的右端点,更新单调队列,首先要保证head始终<= tail,当队尾元素的值sum[que[tail]] > 当前要进队的元素的值sum[j – p]时,队尾的标记tail要前移,tail--;之后队尾元素更新为j – p;对于队首,要保证q[head] > j – q,所以head要++,直到满足。这样更新完成后,队首元素的值就是最小的了,此时在ans与sum[j] – sum[q[head]]间取max。
动态规划,先求一个前缀和sum,ans=max(ans,sum[i]-sum[k])(i-p<=k<=i-q)
根据上式,若ans最大,则sum[k]尽量小,所以单调队列维护区间i-q~i-p的最小值即可。
lon n,P,Q,ans=inf,tmp,sum[maxn];
lon head=1,tail,q[maxn];
int main()
{
    cin>>n>>P>>Q;
    for(int i=1;i<=n;i++)
    {
        cin>>tmp;
        sum[i]=sum[i-1]+tmp;
    }
    for(int i=P;i<=n;i++)
    {
        while(head<=tail&&sum[i-P]<sum[q[tail]])
        tail--;
        q[++tail]=i-P;
        while(head<=tail&&q[head]<i-Q)
        head++;
        ans=max(ans,sum[i]-sum[q[head]]);
    }
    cout<<ans;
    return 0;
}

单调队列 - 有限制的最大和问题

  scanf("%d%d%d",&n,&p,&q);
  for(int i=1; i<=n; i++)
  {
      scanf("%lld",&num[i]);
      num[i]+=num[i-1];
  }

  int ans=0x80000000;
  std::deque<int> deq; //单调队列
  //保存假期的起始点
  //单调队列往往保存的是下标
  for(int i=p; i<=n; i++)
  {
      //单调队列第一步:删去非最优解
      //这一步最重要
      //对于本题而言,如果把之前的数作为起始点还不如把当前点作为起始点,那就删了它
      //如果前几个数的和比i-p对应的数还要大,说明num[j]-num[i-p]比num[j]-num[前几个数]要大
      while(!deq.empty() && num[deq.back()] > num[i-p])
          deq.pop_back();
      //单调队列第二步:保存当前解
      deq.push_back(i-p); //保存起始位置
      //单调队列第三步:删去过时解
      //这一步可以放在任何位置,但必须放在更新答案前
      while(!deq.empty() && deq.front() < i-q)
          deq.pop_front();
      //单调队列第四步:更新答案
      //答案读取的是front,因为根据之前的操作front是最优解
      ans=std::max(ans,int(num[i]-num[deq.front()]));
  }
  printf("%d",ans);

int main()
{
    scanf("%lld %lld %lld", &n, &p, &Q);
    rep(i,1,n)    scanf("%lld", &a),sum[i] = a + sum[i-1];
    rep(i,p,n)
    {
        while(sum[q[tail]] >= sum[i-p] && head <= tail) tail--;//因为i-p处的元素必须入队,所以队中一切比sum[i-p]大的元素必须出队
        q[++tail] = i - p;//把sum[i-p]压入队列
        while(q[head] < i - Q) head++;//因为我们最多只能取到i-q这么长的区间,所以在这个区间之前的所有元素必须出列。
        f[i] = sum[i] - sum[q[head]];
        ans = max(ans, f[i]);
    }
    printf("%lld\n", ans);    
    return 0;
}
X. 
1.线段树   复杂度(nlogn)
2.单调队列 复杂度(n)
具体实现
1.线段树:
首先预处理出来sum前缀和,
对于每一点i,我们只需要找到符合题意范围内最小的即可
并放入线段树中
对去查询每一个点,用线段树去查询i-q+1~i-p+1之间的最小值
然后去更新最大值
2.单调队列:
构造一个单调队列
当枚举到i的时候,用sum[i-p+1]去更新队列

首先,我们想一想怎么算每个“几天内”的最大值,首先想可以暴力,枚举一次天数,再枚举一次i,时间是 O(n2),爆了。
所以我们还要想一想。
前缀和?可以优化……
线段树?能考虑……
这几个小想法组合起来就可以了,但是好像不是很好想。
我们可以枚举第一个休息日的编号i,我们要算从这个第i天开始,往后的P到Q天里快乐指数最大那一天快乐指数是多少,枚举过后取个max就行了。
按这种方式算的话,如何将时间复杂度优化到最小?
考虑前缀和和线段树。
前缀和数组pre维护的是的快乐指数之和,线段树求的是i+P-1 ~ i+Q-1这一段区间的快乐指数前缀和最大值maxn,我们发现maxn-pre[i]就是从这个第i天开始,往后的P到Q天里快乐指数最大那一天快乐指数是多少。
其实求最大值的部分,用st表或者其他的也行,只不过我觉得线段树更好。
总共的复杂度就是O(nlogn)

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts