Vijos 1617 수퍼교주(단조로운 대기열 DP)
4388 단어 OS
1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 using namespace std;
5 int dp[2000001],p[2000001],sum[2000001];
6 int que[2000001];
7 int main()
8 {
9 int n,m,i,str,end;
10 scanf("%d%d",&n,&m);
11 for(i = 1;i <= n;i ++)
12 {
13 scanf("%d",&p[i]);
14 sum[i] = sum[i-1] + p[i];
15 }
16 dp[0] = m;
17 str = end = 0;
18 for(i = 1;i <= n;i ++)
19 {
20 while(str < end&&dp[i-1] - sum[i-1] > dp[que[end-1]]-sum[que[end-1]])
21 end --;
22 que[end++] = i-1;
23 dp[i] = dp[que[str]]-i*100 + sum[i]-sum[que[str]];
24 while(str < end&&dp[que[str]]-(i+1)*100 < 0)
25 str ++;
26 }
27 printf("%d
",dp[n]);
28 return 0;
29 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[OS] 21. Beyond Physical Memory: MechanismsOS는 Page fault가 발생함에 따라 Page fault handler에 정의된대로 이를 처리(swap in)하는데, 이는 Page table에 해당 페이지가 swap 공간의 어느 위치에 저장되어 있는지 저장해...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.