UvaLive 7505 Hungry Game of Ants【dp】

题目链接:

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5527

题意:

已知$n$个蚂蚁初始排列在一条直线,第$i$只蚂蚁位于距离左端点$i$个单位的位置,重量为$i$千克。现每只蚂蚁随机选择向左或向右,以相同的速度前进,遇到端点则掉头,两只蚂蚁相遇时,重量大的蚂蚁吃掉重量小的蚂蚁,如果两只蚂蚁重量一样则左边来的吃掉右边的。问最后有多少种情况最后只有第$k$只蚂蚁存活。
数据范围:$1 \le n \le 10^6$

分析:

对于目标第$k$号蚂蚁,初始必须向左,且要吃掉左边所有蚂蚁。
考虑$i属于[1,k]$,假设最终$[1,i)$构成一只大蚂蚁$A$,$[i,k]$构成一只大蚂蚁$B$,$B$吃掉$A$,为包含所有情况我们要找到最大的$i$使得$\sum_{j=1}^{i} j\le \sum_{j = i+1}^{k-1}j$。其中$[1,i)$之间的蚂蚁随便走,第$i$号蚂蚁必须向左走,$(i,k)$之间的蚂蚁不能乱走必须向右走,方案数为$2^{i-1}$。
现在$k$号蚂蚁和其左边所有蚂蚁构成了一只大蚂蚁,且向右走。
考虑$i属于(k, n]$,假设$i$向左走,$j属于(k,i]$,假设最终$[k,j)$构成一只大蚂蚁$A$,$[j,i]$构成一只大蚂蚁$B$,$A$吃掉$B$。
若设$dp[i]$表示$i$向左走且$[1,i]$之间的蚂蚁都被$k$号蚂蚁吃掉的方案数,不同的$j$表示将$[k,i]$之间的蚂蚁最终分成两只不同大蚂蚁,那么对于该$i$我们要找到最小的$j$使得$\sum_{a=1}^{j-1} a \le \sum_{a=j}^{i}a$,则$dp[i] = \sum_{a=j}^{a=i-1}dp[a]$。
最后求出$dp[n]$,由于第$n$只蚂蚁可以向右走,因此答案即为$dp[n] \times 2$。

代码:

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
/*************************************************************************
> File Name: ecfinal.cpp
> Author: jiangyuzhu
> Mail: 834138558@qq.com
> Created Time: 2016/12/4 18:27:36
************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5, mod = 1e9 + 7;
ll dp[maxn];
ll two[maxn];
ll pre[maxn];
int n, k;
void init()
{
two[1] = 2; pre[1] = 1;
for(int i = 2; i < maxn; ++i){
two[i] = two[i - 1] * 2 % mod;
pre[i] = pre[i - 1] + i;
}
}
int main (void)
{
int T;scanf("%d", &T);
init();
for(int tt = 1; tt <= T; ++tt){
scanf("%d%d", &n, &k);
if(n == 1 && k == 1){
printf("Case #%d: 2\n", tt);
continue;
}
memset(dp, 0, sizeof(dp));
int t1;
for(t1 = 1; t1 <= k; ++t1){
if(pre[t1] >= pre[k] - pre[t1]) break;
}
ll ans = two[t1 - 1];
dp[k] = ans;
int l = k;
for(int i = k + 1; i <= n; ++i){
while(l < i && pre[l] < pre[i] - pre[l]) ans = (ans - dp[l++] + mod) % mod;
dp[i] = ans;
ans = (ans + dp[i]) % mod;
}
printf("Case #%d: %lld\n", tt, dp[n] * 2 % mod);
}
return 0;
}
文章目录
  1. 1. 题目链接:
  2. 2. 题意:
  3. 3. 分析:
  4. 4. 代码: