首页 > 程序开发 > 综合编程 > 其他综合 >

【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;
}
相关文章
最新文章
热点推荐