【UVALive 7505】Hungry Game of Ants（DP）

2016-10-29

一条链上n只蚂蚁，第i只蚂蚁的weight为i。每只蚂蚁会选择一个初始方向，向左或向右。两只蚂蚁相遇时，大体重的蚂蚁会吃掉小体重蚂蚁，并增加上小体重蚂蚁的体重。如果两只蚂蚁体重相同，左边的会吃掉右边的。最左最右为边界，蚂蚁碰到边界会掉头。

题目大意：
一条链上n只蚂蚁，第i只蚂蚁的weight为i。每只蚂蚁会选择一个初始方向，向左或向右。两只蚂蚁相遇时，大体重的蚂蚁会吃掉小体重蚂蚁，并增加上小体重蚂蚁的体重。如果两只蚂蚁体重相同，左边的会吃掉右边的。最左最右为边界，蚂蚁碰到边界会掉头。

现在给所有蚂蚁定义初始方向，问有多少中方案能让第K只蚂蚁最终存活下来。

首先明确：第K只蚂蚁想要存活，初始方向一定不是向右（除非k == n)
，其次，它会把左边所有蚂蚁吃掉然后掉头。

这样先考虑k吃掉左边蚂蚁并掉头的方案数，其实就是找一个最大的j，满足
∑j > ∑1≤c≤jant[c]

即k把j+1到k的蚂蚁都吃掉后，能吃掉1到j合并后剩下的那只蚂蚁。

因为对于每只蚂蚁，向右走一定会被吃掉。所以1~j的蚂蚁可以随意选择方向，并且保证了最坏情况也能被解决。j+1到k-1的蚂蚁都向右（被k吃掉），因为如果有任何一个选择向左，就会与1~j合并，最后变成一只蚂蚁来吃掉k。这样方案就是2j

然后考虑调头后，对于第i只蚂蚁，如果向左走，有一个可以走的最远（离k最近）的地方j，满足
∑1≤c=∑j≤c≤iant[c]，即j到i合并，k吃掉左边的再吃到j-1。
对于较大的j，这个不等式都满足，对于较小的j，这个条件都不满足。

这样，其实就是j到k-1的蚂蚁随意选择方向，k+1到j-1都要被k吃掉变成一只。即dp[i]=∑j≤c，dp[j]表示k+1到j的蚂蚁都被k吃掉的方案数，并且此时k方向一定是朝右。

这样就可以遍历一遍，然后维护一个指针，指向最小的j，每次转移前向右移动到适合的位置，在一个全局的SUM上维护j到i的区间dp值即为dp[i]的值。

需要注意最后答案是dp[n]*2，因为第n个蚂蚁向右走和向左等价。

代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#define LL long long
#define Pr pair
#define fread(ch) freopen(ch,"r",stdin)
#define fwrite(ch) freopen(ch,"w",stdout)

using namespace std;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-8;
const int maxn = 1123456;

LL dp[maxn];

LL Pow(LL a,LL b)
{
    LL ans = 1;

    while(b)
    {
        if(b&1) ans = ans*a%mod;
        b >>= 1;
        a = a*a%mod;
    }

    return ans;
}

LL Sum(LL x)
{
    return x*(x+1)/2;
}

LL Search(LL l,LL r,LL k)
{
    if(r < l) return 1;
    LL sum = Sum(r);
    LL ans = -1;

    while(l <= r)
    {
        LL mid = (l+r)>>1;

        if(sum-Sum(mid)+k > Sum(mid))
        {
            ans = mid;
            l = mid+1;
        }
        else r = mid-1;
    }

    if(ans == -1) return 0;

    return Pow(2,ans);
}

LL solve(int n,int k)
{
    LL ans = 0;

    dp[k] = Search(1,k-1,k);
    int l = k;
    ans = dp[k];

    for(int i = k+1; i <= n; ++i)
    {
        while(l < i && Sum(l) < Sum(i)-Sum(l)) ans = ((ans-dp[l++])%mod+mod)%mod;

        dp[i] = ans;
        ans = (ans+dp[i])%mod;

    }

    return dp[n]*2%mod;
}

int main()
{
    //fread("");
    //fwrite("");

    int t,n,k;

    scanf("%d",&t);

    for(int z = 1; z <= t; ++z)
    {
        scanf("%d%d",&n,&k);
        printf("Case #%d: %lld\n",z,solve(n,k));
    }

    return 0;
}