首页 > 代码库 > UVALive 4726 Average ——（斜率优化DP）

UVALive 4726 Average ——（斜率优化DP）

2024-09-14 19:41:04   216人阅读

　　这是第一次写斜率优化DP= =。具体的做法参照周源论文《浅谈数形结合思想在信息学竞赛中的应用》。这里仅提供一下AC的代码。

　　有两点值得注意：1.我这个队列的front和back都是闭区间的；2.在while(...) front++; 这个循环里面，<=写成<就会WA，不知道是为何（讲道理是肯定没问题的，至多多判断几个点而已，我猜想可能是存在了精度误差导致的）。。

　　代码如下：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <math.h>
 5 using namespace std;
 6 const int N = 1e5 + 100;
 7 
 8 int n,m;
 9 int pre[N];
10 char s[N];
11 int que[N];
12 double cal(int x,int y)
13 {
14     return 1.0 * (pre[y] - pre[x]) / (y - x);
15 }
16 
17 int main()
18 {
19     int T;
20     scanf("%d",&T);
21     while(T--)
22     {
23         scanf("%d%d",&n,&m);
24         scanf("%s",s+1);
25         for(int i=1;i<=n;i++) pre[i] = pre[i-1] + s[i] - ‘0‘;
26         int front = 0, back = -1;
27         int ansl = 0, ansr = m;
28         double ans = cal(0, m);
29         int len = m;
30         for(int i=m;i<=n;i++)
31         {
32             int a = i - m;
33             while(front < back && cal(que[back], a) <= cal(que[back-1], a)) back--;
34             que[++back] = a;
35             while(front < back && cal(que[front], i) <= cal(que[front+1], i)) front++;
36             double temp = cal(que[front], i);
37             if(temp > ans)
38             {
39                 ans = temp;
40                 ansl = que[front];
41                 ansr = i;
42                 len = i - que[front];
43             }
44             else if(fabs(temp-ans) < 1e-8 && len > i - que[front])
45             {
46                 len = i - que[front];
47                 ansl = que[front];
48                 ansr = i;
49             }
50         }
51         printf("%d %d\n",ansl + 1, ansr);
52     }
53     return 0;
54 }

 

UVALive 4726 Average ——（斜率优化DP）


联系
我们