DP优化 学习小结_机械优化方法小结

DP优化 学习小结由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“机械优化方法小结”。

DP优化 学习小结

2010-08-27 15:55

这两天简单学习了一些动态规划的优化技巧，感觉自己的数学实在太弱了，虽然大概知道怎么用，但很多证明自己理解的还不是很透。

关于用单调队列优化的动态规划以前整理过一些，可以看这里：【单调队列 学习小结】

四边形不等式优化

主要是对于dp（i，j）的决策点 s（i，j），通过单调性证明 s（i，jpo[p2].y)/(po[p1].xsum[arr[head]]);po[i].x = a * sum[i];

po[i].y = dp[i] + a * sum[i] * sum[i]po[p2].y)/(po[p1].xf[p2]f[p2]f[arr[head]]f[arr[head]]sum[p2]p2);

}

inlinelonglong SS(int p1, int p2){

return num[p1 +1]sum[p1] + p1 * num[p1 +1]sum[p2] + p2 * num[p2 +1]);

}

inlinebool rate(int p1, int p2, int p3){

if(GG(p1, p2)* SS(p2, p3)>= GG(p2, p3)* SS(p1, p2))returnfalse;elsereturntrue;

}

int main(int argc, char** argv){

while(scanf(“%d%d”, &n, &m)!= EOF){

for(int i =1;i

sort(num +1, num + n +1);

sum[0] =0;

for(int i =1;i

int head =0, rear =0;

arr[++rear] =0;

for(int i = m;i

for(int k = head +1;k

if(cal(i, arr[k])

}

dp[i] = cal(i, arr[head]);

if(im +1;

while(head +2

if(rate(arr[rear-2], arr[rear-1], arr[rear])==false){arr[rear-1] = arr[rear];

rear-=1;

} elsebreak;

}

}

cout

}

return(EXIT_SUCCESS);

}