.org pro char git int a* sin 队列 tdi
题目链接
设c[i]是战斗力前缀和,f[i]是考虑前i个,且最后一组分到第i个士兵为止的战斗力之和
则有朴素状态转移方程
- for(int i=1;i<=n;++i)
- for(int j=0;j<i;++j){
- int x=c[i]-c[j];
- f[i]=min(f[i],a*x*x+b*x+c);
- }
然后考虑优化。
假设f[i]最优结果是从f[j]转移过来,同时有一个不那么优的转移f[k]
则有$f[j]+a*squa(c[i]-c[j])+b*(c[i]-c[j])+c>f[k]+a*squa(c[i]-c[k])+b*(c[i]-c[k])+c$
展开得到$f[j]+a*squa(c[i])+a*squa(c[j])-2*a*c[i]*c[j]+b*c[i]-b*c[j]>f[k]+a*squa(c[i])+a*squa(c[k])-2*a*c[i]*c[k]+b*c[i]-b*c[k]$
整理有$f[j]+a*squa(c[j])-2*a*c[i]*c[j]-b*c[j]>f[k]+a*squa(c[k])-2*a*c[i]*c[k]-b*c[k]$
于是有$\frac{(f[j]+a*c[j]^{2}-b*c[j])-(f[k]+a*c[k]^{2}-b*c[k])}{2*a*(c[j]-c[k])}>c[i]$
于是可以单调队列优化DP
- #include < cstdio > #include < cstdlib > #include < cstring > #include < cctype > #include < algorithm > using namespace std;
- inline long long read() {
- long long num = 0,
- f = 1;
- char ch = getchar();
- while (!isdigit(ch)) {
- if (ch == ‘ - ‘) f = -1;
- ch = getchar();
- }
- while (isdigit(ch)) {
- num = num * 10 + ch - ‘0‘;
- ch = getchar();
- }
- return num * f;
- }
- long long sum[1002000];
- long long f[1002000];
- long long d[1002000];
- long long a,
- b,
- c;
- inline long long squa(long long x) {
- return x * x;
- }
- inline double count(int x, int y) {
- return ((f[x] + a * d[x] - b * sum[x]) - (f[y] + a * d[y] - b * sum[y])) / (2.0 * a * (sum[x] - sum[y]));
- }
- int s[1002000];
- int h,
- t;
- int main() {
- int n = read();
- a = read();
- b = read();
- c = read();
- for (int i = 1; i <= n; ++i) {
- sum[i] = read() + sum[i - 1];
- d[i] = squa(sum[i]);
- f[i] = -1e18;
- }
- for (int i = 1; i <= n; ++i) {
- while (h < t && count(s[h], s[h + 1]) <= sum[i] * 1.0) h++;
- int x = s[h];
- f[i] = f[x] + a * squa(sum[i] - sum[x]) + b * (sum[i] - sum[x]) + c;
- while (h < t && count(s[t - 1], s[t]) >= count(s[t], i)) t--;
- s[++t] = i;
- }
- printf("%lld", f[n]);
- return 0;
- }
【Luogu】P3628特别行动队(斜率优化DP)
.org pro char git int a* sin 队列 tdi
原文:http://www.cnblogs.com/cellular-automaton/p/7977901.html
来源: http://www.bubuko.com/infodetail-2417097.html