●HDU 3507 Print Article

时间:2022-06-07 09:46:57

题链:

斜率优化DP
一个入门题,就不给题解了,网上的好讲解很多的。
 
这里就只提一个小问题吧(好吧,个人觉得这个问题也不小)。
本题的输入数据 A[i] 可能会有很讨厌的 0 出现,
这样的话,完全可能导致 k<j,SUM[k]==SUM[j],DP[k]==DP[j]的情况出现,
 
所以用double型计算斜率肯定会错啦,因为分母会被减成 0,鬼知道会算出来一个什么。
 
另外这样写也会出错: 
在计算完当前的DP值然后入队时,如果采用这种写法,就会WA。
(新点与队列里倒数第一个点的斜率 < 队列里倒数第一个点和倒数第二个点的斜率 时才弹出队尾。)
●HDU 3507 Print Article
正确的应该写成小于等于就弹出
(新点与队列里倒数第一个点的斜率 <= 队列里倒数第一个点和倒数第二个点的斜率 时弹出队尾。)
●HDU 3507 Print Article
让我们来看看为什么会这样?
同样是会出现 k<j,SUM[k]==SUM[j],DP[k]==DP[j]的情况,
那么由本题的解法,计算斜率时,令 X[j]=2*SUM[j],Y[j]=DP[j]-SUM[j]*SUM[j]
那么反映到平面上,k(X[k],Y[k]),j(X[j],Y[j])就是两个重合的点
●HDU 3507 Print Article
这时,如果这两个点都在队列里,(假设j在队尾,k在队列倒数第二个),且又来了一个如下图的新点i要加进队列,会怎样呢?
●HDU 3507 Print Article
按算法的逻辑,计算得到i与j的斜率并没有小于j与k的斜率,(再看看判断语句,两边都乘了0),
所以接下来就退出了“弹出队尾”的while循环,然后,我们的下凸包也就没有被维护好:
●HDU 3507 Print Article
所以自然错了。
综上,对于本题,因为有0的出现,只有采取 <= 的写法(且不用double计算)才能顺利完成这个入门题。(汗...)
(有点类似求凸包,也要避免重复点带来的影响。)
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 500050
using namespace std;
int DP[MAXN],SUM[MAXN];
int N,M;
int dx(int a,int b){
return 2*(SUM[a]-SUM[b]);
}
int dy(int a,int b){
return (DP[a]+SUM[a]*SUM[a])-(DP[b]+SUM[b]*SUM[b]);
}
int main(){
static int q[MAXN],l,r;
while(~scanf("%d%d",&N,&M)){
for(int i=1;i<=N;i++)
scanf("%d",&SUM[i]),SUM[i]+=SUM[i-1];
l=1; r=1; q[1]=0;
for(int i=1;i<=N;i++){
while(l+1<=r&&dy(q[l+1],q[l])<=SUM[i]*dx(q[l+1],q[l])) l++;
DP[i]=DP[q[l]]+(SUM[i]-SUM[q[l]])*(SUM[i]-SUM[q[l]])+M;
while(l+1<=r&&dy(i,q[r])*dx(q[r],q[r-1])<=dy(q[r],q[r-1])*dx(i,q[r])) r--;
q[++r]=i;
}
printf("%d\n",DP[N]);
}
return 0;
}