[USACO16JAN]愤怒的奶牛Angry Cows

传送门

一道神奇的DP………（鬼知道他为什么在tarjan里面）

一开始可能会考虑贪心或者什么其他神奇的算法，不过还是DP比较靠谱。

我们用f[i]表示摧毁所有i左侧的炸药包最少需要的能量，用g[i]表示摧毁所有i右侧的炸药包最少需要的能量。

那么我们只要找到满足j < i,a[i] - a[j] > f[j]+1的最后一个j炸药包，就可以更新f[i]的值，f[i] = min(f[i],a[i]-a[j],f[j]+1);

同样的g也是同理。

为什么这么找呢……因为首先我们发现如果a[i]-a[j]比f[j]+1还要小的话，那么从i点引发的爆炸是可以波及到j点的，所以并不需要更新答案，直到不满足的时候我们才更新。

最后枚举爆炸的点就可以了。

然后这题有个技巧，如果往数轴上投炸药你要么投在点上要么投在两者中间，也就是只可能有整数或者.5的情况。这样直接把所有数据×2计算最后/2就可以了。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<queue>

#include<set>

#include<map>

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

using namespace std;

typedef long long ll;

const int M = ;

const int INF = ;

int read()

{

    int ans = ,op = ;

    char ch = getchar();

    while(ch < '' || ch > '')

    {

    if(ch == '-') op = -;

    ch = getchar();

    }

    while(ch >= '' && ch <= '')

    {

    ans *= ;

    ans += ch - '';

    ch = getchar();

    }

    return ans * op;

}

int n,f[M],g[M],a[M],head,tail,ans = INF;

int main()

{

    n = read();

    rep(i,,n) a[i] = read() << ;

    sort(a+,a++n);

    n = unique(a+,a++n) - a - ;

    rep(i,,n) f[i] = g[i] = INF;

    f[] = -;

    rep(i,,n)

    {

    while(head +  < i && a[i] - a[head+] > f[head+] + ) head++;

    f[i] = min(f[head+] + ,a[i] - a[head]);

    }

    g[n] = -,tail = n;

    per(i,n-,)

    {

    while(tail -  > i && a[tail-] - a[i] > g[tail-] + ) tail--;

    g[i] = min(a[tail] - a[i],g[tail-] + );

    }

    //rep(i,1,n) printf("%d %d\n",f[i],g[i]);

    head = ,tail = n;

    while(head < tail)

    {

    ans = min(ans,max((a[tail] - a[head]) >> , + max(g[tail],f[head])));

    if(f[head+] < g[tail-]) head++;

    else tail--;

    }

    printf("%.1lf\n",(double)ans / 2.0);

    return ;

}

巴特西

[USACO16JAN]愤怒的奶牛Angry Cows

最新文章

热门文章