需要看出点东西的 dp 题。
题目链接。
题意
现在有 个小怪，第 个的生命值是 。
现在你可以进行攻击，一次攻击会给所有或者的小怪造成
的伤害，此时如果有小怪死了，将会再自动进行一次攻击。
如果一次攻击后，有多个小怪同时死亡，只会触发一次攻击。
现在你可以花
的代价，将一个小怪的生命值 或
，问最小的代价，使得最终只使用一次攻击就能击杀所有小怪。
。
题解
若更改完成后，所有小怪的生命值最大是 。
那么这个条件相当于，生命值为 的小怪至少各有一个。
还可以发现，若两个小怪
初始生命值满足 ，那么他们的最终生命值一定满足
。
那么可以首先将
升序排序，这样小怪的最终生命值序列一定不降。
此时可以进行 dp，设
表示第 个小怪最终生命值是 ，前 个小怪的代价最小是多少。
有 dp 方程 。
考虑从这个 dp
方程里面能不能发现一点东西，想想每一个状态应该可以往哪里转移。
首先可以发现，如果有 ，那么 转移到 显然是没用的。
因为此时如果转移到
的话，这一步的代价一定更优，之后的代价一定不劣。
所以此时没有必要转移到 。
还可以发现，如果有 ，那么 转移到 也是没有必要的。
为什么呢，因为考虑如果 ，那么一定也有 。
那么此时应该有 ，此时更应该让 转移到 去。
所以此时也没有必要转移到 。
此时只有 的状态会同时向
和 转移。
那么这个时候就好做了，直接上线段树就可以做到 。
考虑更快一点的做法，使用两个栈，分别维护 和 。
我们需要支持的操作有插入、弹出、以及给整个栈加一个等差数列。
栈内维护所有元素的二阶差分序列即可。时间复杂度 。
代码
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
using di=pair<double,int>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const ll MAX=10000000000000ll;
struct node
{
ll v[1100005];
int len;
inline void ins(ll V)
{
if(len>=1) v[len-0]-=2*V;
if(len>=2) v[len-1]+=V;
v[++len]=V;
}
inline ll pop()
{
if(!len) return MAX;
ll V=v[len--];
if(len>=1) v[len-0]+=2*V;
if(len>=2) v[len-1]-=V;
return V;
}
inline void add(ll k,ll b)
{
if(len>=1) v[len]+=k;
if(len>=2) v[len-1]+=b-k;
}
inline ll get()
{
ll ans=MAX,pre1=0,pre2=0;
for(int i=len;i;i--)
{
pre1+=v[i];
pre2+=pre1;
ans=min(ans,pre2);
}
return ans;
}
}T[2];
int a[1000005];
int n;ll val;
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=read();
sort(a+1,a+n+1);
for(int i=1;i<=n+1;i++) T[1].ins(MAX);
int j=0;ll v=0;
for(int i=1;i<=n;i++)
{
if(a[i]>i) val+=a[i]-i,a[i]=i;
while(j<a[i])
{
T[0].ins(v);
v=T[1].pop();
j++;
}
T[1].ins(v);
v=min(v,T[0].pop());
T[1].add(1,1),T[0].add(1,1);
}
ll ans=min(T[0].get(),T[1].get());
printf("%lld\n",val+min(ans,v));
return 0;
}
|