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 }

 
 
 

좋은 웹페이지 즐겨찾기