BZOJ 3437: 小P的牧场

这题一看就是奇怪的dp啊╮(╯_╰)╭
f[i]表示考虑前i个牧场 且第i个有取的最小代价
但是把这个方程列出来 会发现这个方程有一部分的系数是一个公差为1的等差数列
这就很蛋疼
不能以一个项数为O(1)级的多项式表示i取j决策的代价

怎么办呢
所谓正难则反
首先设答案为类似只在n+1号位置取一个观察站 的代价
如果这时候在i位置取一个观察站 则答案会减少(sum[i] * (n – i) – a[i])
f[i]表示考虑i~n的牧场 最多可以扣掉多少代价 且i有取
方程为
f[i] = max(a[i] + f[j] + sum[i] * (j – i))
sum[i]表示Σ(b[j])(1 <= j <= i) 这个方程拿去斜率优化一下即可 另外这个系列的数据范围巨坑无比 n的范围是100w 他写变成n <= 1000000,0 后面加了个,0不知道作何心态=-=

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const ll maxn = 1000 * 1000 + 5;
 
struct poll
{
    ll x, y;
    poll(ll a = 0, ll b = 0) : x(a), y(b) {}
};
 
poll q[maxn];
ll f[maxn], n, a[maxn], b[maxn], sum[maxn], h, t;
ll ans;
 
ll xj(poll a, poll b, poll c)
{
    return ((ll)b.x - a.x) * (c.y - a.y) - ((ll)b.y - a.y) * (c.x - a.x);
}
 
ll calc(ll i, poll j)
{
    return -a[i] + j.y + sum[i] * (j.x - i);
}
 
int main()
{
    scanf("%lld", &n);
    for (ll i = 0; i < n; ++i)
        scanf("%lld", &a[i]);
    for (ll i = 0; i < n; ++i)
    {
        scanf("%lld", &b[i]);
        ans += ((ll)n - i) * b[i];
        if (!i) sum[i] = b[i];
        else sum[i] = sum[i - 1] + b[i];
    }
    f[n - 1] = sum[n - 1] - a[n - 1];
    h = t = 0;
    q[0] = poll(n - 1, f[n - 1]);
    ll as = f[n - 1];
    for (ll i = n - 2; i >= 0; --i)
    {
        while (h < t && calc(i, q[h]) <= calc(i, q[h + 1])) ++h;
        f[i] = calc(i, q[h]);
        while (h < t && xj(q[t - 1], q[t], poll(i, f[i])) <= 0) --t;
        q[++t] = poll(i, f[i]);
        as = max(as, f[i]);
    }
    printf("%lld", ans - as);
}

BZOJ 1713: [USACO2007 China]The Bovine Accordion and Banjo Orchestra(baabo)

这题的方程很显然
f[i][j] = A[i]*B[j] + max(f[k][l] – (sumA[i – 1] – sumA[k]) ^ 2 – (sumB[j – 1] – sumB[l]) ^ 2);
二维斜率优化?维护一个立体凸壳?每次用一个平面区更新?
呵呵= =’
呵呵呵呵
呵呵呵呵呵呵呵呵
呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵
显然是想多了= =
我们可以发现
对于状态 i,j 决策k,l比如满足k=i-1 or l=j-1
这个想一下就会知道 显然你让两坨牛去喝酒还不让让它们去唱歌= =

考虑l=j-1 的情况(另同)
f[i][j] = A[i]*B[j] + max(f[k][j-1] – sumA[i – 1]^2 + 2*sumA[i-1]*sumA[k] – sumA[k] ^ 2);

x = 2*sumA[k]
y = f[k][j-1]-sumA[k]^2
a = sumA[i-1]

斜率优化之即可

这样看似就可以O(n^2) 水过了?

呵呵= =’
呵呵呵呵
呵呵呵呵呵呵呵呵
呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵呵
显然是想多了= =
正常的想法是维护两个分别为=i-1和=j-1的单调队列
但是
显然i和j是会变的- –
对于每个i 新开一个对列来维护倒是额可以
对于j呢?
开n个全局单调队列维护之!
然后就各种science了~
边界是对于每个队列开始都加入一个x=y=0的点
f[i][0] = f[0][j] = -0x7fffffff;
f[0][0] = 0;

——————————code————————-

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <cstdlib>
#include <functional>
#include <cmath>
#include <map>
#include <vector>
#include <ctime>
using namespace std;
typedef long long ll;
const ll maxn = 1005;
struct poll
{
  ll x, y, t;
  poll (ll a = 0, ll b = 0, ll c = 0) : x(a), y(b), t(c) {}
};
struct qu
{
  ll h, t;
  poll p[maxn];
}q[maxn];
ll n, a[maxn], b[maxn], suma[maxn], sumb[maxn], f[maxn][maxn];
inline ll sqr(ll a) { return a * a; }
ll get_ans(ll i, ll j, ll x, ll y)
{
  /*ll k = (!x || !y) ? sqr(suma[i – 1]) + sqr(sumb[j – 1]) : ;
  if (i == n || j == n) k += sqr(suma[n] – suma[i]) + sqr(sumb[n] – sumb[j]);*/
  return a[i] * b[j] + f[x][y] – sqr(suma[i – 1] – suma[x]) – sqr(sumb[j – 1] – sumb[y]);
}
ll get(qu &q, ll a)
{
  while (q.t – q.h > 1 && q.p[q.h].y + a * q.p[q.h].x <= q.p[q.h + 1].y + a * q.p[q.h + 1].x) q.h++;
  return q.p[q.h].t;
}
ll xj(poll a, poll b, poll c)
{
  return (b.x – a.x) * (c.y – b.y) – (b.y – a.y) * (c.x – b.x);
}
void add(qu &q, ll x, ll y, ll t)
{
  poll k = poll(x, y, t);
  while (q.t – q.h > 1 && (xj(q.p[q.t – 2], q.p[q.t – 1], k) >= 0)) q.t–;
  q.p[q.t++] = k;
}
int main()
{
  freopen(“input.in”, “r”, stdin);
  freopen(“output.out”, “w”, stdout);
  scanf(“%I64d”, &n);
  for (ll i = 1; i <= n; i++) scanf(“%I64d”, &a[i]);
  for (ll i = 1; i <= n; i++) scanf(“%I64d”, &b[i]);
  for (ll i = 1; i <= n; i++) suma[i] = suma[i – 1] + a[i], sumb[i] = sumb[i – 1] + b[i], f[i][0] = f[0][i] = -0x7fffffff;
  f[0][0] = 0;
  for (ll i = 1; i <= n; i++) q[i].p[q[i].t++] = poll(0, 0, 0);
  ll ans = 0;
  for (ll i = 1; i <= n; i++)
  {
    q[0].h = 0;
    q[0].t = 1;
    q[0].p[0] = poll(0, 0, 0);
    for (ll j = 1; j <= n; j++)
    {
      ans = max(
                  ans,
                  (f[i][j] = max(
                                   -sqr(suma[i – 1]) – sqr(sumb[j – 1]),
                                   max(
                                         get_ans(i, j, get(q[j], suma[i – 1]), j – 1),
                                         get_ans(i, j, i – 1, get(q[0], sumb[j – 1]))
                                      )
                                )
                  ) – sqr(suma[n] – suma[i]) – sqr(sumb[n] – sumb[j])
                );
      add(q[j], 2 * suma[i], f[i][j – 1] – sqr(suma[i]), i);
      add(q[0], 2 * sumb[j], f[i – 1][j] – sqr(sumb[j]), j);
    }
  }
  printf(“%I64d”, ans);
  fclose(stdin);fclose(stdout);
}

 

斜率优化

 

在被坑爹的斜率优化虐了1week之后。。终于出头了o(∩_∩)o…哈哈

 

在思考了一个晚上要怎么纪念悲剧的结束之后-写了一下这个boring的thing
——————————————————————————————————————–

1010: [HNOI2008]玩具装箱toy

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 2506  Solved: 834
[Submit][Status][Discuss]

 

 

 

 

Description

P教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中。P教授有编号为1…N的N件玩具,第i件玩具经过压缩后变成一维长度为Ci.为了方便整理,P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具,那么两件玩具之间要加入一个单位长度的填充物,形式地说如果将第i件玩具到第j个玩具放到一个容器中,那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目,他可以制作出任意长度的容器,甚至超过L。但他希望费用最小.

Input

第一行输入两个整数N,L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7

Output

输出最小费用

Sample Input

5 4
3
4
2
1
4

Sample Output

1

HINT

Source

——————————————————————————————————————–
上面是一个经典的斜率优化题目。。
为了突出斜率优化的优势 不妨设n<=1000000~
此时nlgon就一边去吧~~
经过深思熟虑 不难得出本题的O(N^2)的方程:f[i]=min(f[j]+(c[i]-c[j]-L-1)^2)
其中 f[i]表示前i个玩具放完的最小$$
       c[i]=前i个玩具长的和+i
为什么这样定义?、因为如果直接用前i个玩具长的和的话 j+1~i 塞在一堆表示是c[i]-c[j]+i-j-1
so麻烦啊
so。。。
然后吧方程化开 =f[j]+(c[i]-1-L)^2+c[j]^2-2*c[i]*c[j]+2*c[j]+2*L*c[j];
再把所有项里跟j完全无关的都干掉(因为那些对于判断哪个j比较优没影响)
=>   f[j]+c[j]^2-2*c[i]*c[j]+2*c[j]+2*L*c[j]
<你不干掉也nothing。。但是还是干掉好。。。>
再把所有只和j有关的项扔在一起:
 f[j]+c[j]^2+2*c[j]+2*L*c[j]     -2*c[i]*c[j]
然后把只和j有关的项扔在一起的设为y , y=f[j]+c[j]^2+2*c[j]+2*L*c[j]
再设呢个有i有j的项里的和j有关的东西设为x,x=c[j]
然后~  f[i]=y-2*c[i]*x
       =>y=2*c[i]*x+f[i]
对于每个点i有一个在坐标系上的坐标(c[i],f[i]+c[i]^2+2*c[i]+2*L*c[i])
因为斜率(2*c[i])单调上升所以可以用单调队列维护一个凸壳(方程取min的是维护下凸壳  max为上)
判断head能不能用的方法就是:
对于现在的i可以设有一个斜率为2*c[i]的直线从灰常灰常远的地方灰了过来
 第一个切到那个凸壳的时刻 切到凸壳的那个角的值就是对于这个i最优的j
然后f[i]就可以出来啦~~~
怎么判断时候切到呢 先把队列的head和队列的head+1比较:
把斜率2*c[i]带入两个点 分边求出一个b(即为y=2*c[i]*x+f[i]中的f[i])
比较其大小 如图:psb
显然绿(head)的b>蓝(head+1)的b
下一个点同理
但是只要一到切点 就。。。。

psb (1)

 

蓝>绿~~~~

而且对于i上升 i的斜率也会上升 所以他们切那个凸壳的切点只会越来越后面
也就是对于前面删除的点 后面不用在考虑了~
最后一步是维护凸壳 相当于加入一个坐标(c[i],f[i]+c[i]^2+2*c[i]+2*L*c[i])
再把 i tail tail-1三个判断:向量tail -> i 指向 向量tail-1 -> tail的左或右
对于下凸壳 左就说明是凸壳 右就不是 要dec(tail)
对于上凸壳反之.
CODE:
 
#include <cstdio>
const int maxn=200005;
long long team[maxn],f[maxn],c[maxn],y[maxn];
bool work(int i,int j,int k)
{
  if (y[j]-2*c[i]*c[j]>y[k]-2*c[i]*c[k]) return true;else return false;
}
// 判断直线和凸壳的切点
//这段程序在别的程序各种变形都是差不多的 只是我们判断的方法不一样 结果是一样的~
bool del(int i,int j,int k)
{
  if ((c[j]-c[k])*(y[i]-y[j])-(c[i]-c[j])*(y[j]-y[k])<0) return true;
  else return false;
}
//维护凸壳
//向量的叉乘? 好像是叫这个 。。。
int main()
{
freopen(“bzoj1010.in”,”r”,stdin);
freopen(“bzoj1010.out”,”w”,stdout);
  int n;long long l;
  scanf(“%d%I64d”,&n,&l);
  for (int i=1;i<=n;i++)
  {
    scanf(“%I64d”,&c[i]);
    c[i]+=c[i-1];
  }
  int h=0;int t=0;
  //一开始让h=t可以让队列的第一个值代表j=0(就是全部玩具在一起) 就不用特判了
  for (int i=1;i<=n;i++) c[i]+=i;
  for (int i=1;i<=n;i++)
  {
    while (h<t && work(i,team[h],team[h+1])) h++;
    int j=team[h];
    f[i]=f[j]+(c[i]-c[j]-l-1)*(c[i]-c[j]-l-1); //team[h]直接就是对于i的最优解了
    y[i]=f[i]+c[i]*c[i]+2*c[i]*(l+1);
    while (h<t && del(i,team[t],team[t-1])) t–;
    t++;
    team[t]=i;
  }
  printf(“%I64d”,f[n]);
fclose(stdin);fclose(stdout);
}
ps:如果斜率不是递增的也是可以做的 但是要nlogn就是了 而且据说极其麻烦= =。。
 
再次ps:如果斜率递减就反过来做 就递增了~  注意维护凸包那里会不一样!<被这个坑了很久 …..>