适合在线做笔试的网站,网站备案密码收不到,机关内网站建设方案书,昆明网站免费制作斜率优化问题一般都是决策单调问题。对于这题能够证明单调决策。 令sum[i]sigma(c [k] ) 1ki , f[i]sum[i]i , cL1; 首先我们能够写出转移方程 dp[i] min( dp[j] (f[i]-f[j]-c)^2 ) 。令决策j1j2。若决策j2更优有 dp[j2](f[i]-f[j2]-c)^2dp[j1](f[i]-f[… 斜率优化问题一般都是决策单调问题。对于这题能够证明单调决策。 令sum[i]sigma(c [k] ) 1ki , f[i]sum[i]i , cL1; 首先我们能够写出转移方程 dp[i] min( dp[j] (f[i]-f[j]-c)^2 ) 。令决策j1j2。若决策j2更优有 dp[j2](f[i]-f[j2]-c)^2dp[j1](f[i]-f[j1]-c)^2 能够得带 ((dp[j2]f[j2]^2)-(dp[j1]f[j1]^2) )/(f[j2]-f[j1])2*(f[i]-c)。 优于f[i]是递增的所以对于ti的点。决策j2总是比j1更优。那么j1实际上能够从决策集合中删除。后面的就能够用一个队列维护了。 span stylefont-size:14px;#include set
#include map
#include queue
#include stack
#include cmath
#include string
#include cctype
#include cstdio
#include cstdlib
#include cstring
#include iomanip
#include iostream
#include algorithm
using namespace std;
typedef long long LL;
const int inf 0x3fffffff;
const int mmax 50010;
LL C[mmax];
LL L,c;
LL sum[mmax],f[mmax],dp[mmax];
LL sqr(LL x)
{return x*x;
}
double G(int x)
{return 1.0*f[x]*f[x]dp[x];
}
double S(int x)
{return 2.0*f[x];
}
void calc(int i,int j)
{dp[i]dp[j]sqr(f[i]-f[j]-c);
}
int Q[mmax];
int main()
{int n;while(cinnL){cL1;sum[0]0;f[0]0;for(int i1;in;i){scanf(%lld,C[i]);sum[i]sum[i-1]C[i];f[i]sum[i]i;}int head0,tail-1;dp[0]0;Q[tail]0;for(int i1;in;i){while(headtail){double tmp1.0*(G(Q[head1])-G(Q[head]))/(S(Q[head1])-S(Q[head]));if(tmpf[i]-c)head;elsebreak;}calc(i,Q[head]);while(headtail){double tmp11.0*(G(Q[tail])-G(Q[tail-1]))/(S(Q[tail])-S(Q[tail-1]));double tmp21.0*(G(i)-G(Q[tail]))/(S(i)-S(Q[tail]));if(tmp1tmp2)tail--;elsebreak;}Q[tail]i;}printf(%lld\n,dp[n]);}return 0;
}
/span转载于:https://www.cnblogs.com/yangykaifa/p/6780636.html
