题解 P4945 【最后的战役】
Nemlit
2018-10-27 19:36:45
听说本题正解是DP,但是貌似有别的做法。
这道题需要实现三个操作:
1.收集 $[1,i]$ 层魔法中魔法类型为 $x_i$的魔法能量
2.收集 $[1,i]$ 层中魔法能量最大那层的魔法能量
3.使用加倍魔法
第一个操作需要查找所有$x_i$类型的魔法,那么我们可以用一个数组记下来。但是我们发现$x_i$到了$10^9$级别,直接用数组空间显然会炸。但是我们也可以发现$n$非常小,所以我们考虑离散化,用$map$或排序去重均可。
第二个操作比较简单,只需要每一次新枚举一个元素就更新最大值即可
那么问题来了,第三个操作怎么办呢?显然我们可以用$DP$来实现,不过这样时间消耗至少是$O(nm)$,那有没有什么更快的方法呢?
我们可以用贪心来实现。
但是我们怎么贪心呢?
按照常规的思路,我们可以求出所有的值之后按照从小到大的顺序,再在最大的前面翻倍。但是这样是不是对的呢??
我们来看一组反例:假设我们求出的答案为$1$ $7$ $9$,我们可以用一次翻倍,按照刚刚的贪心思路,我们要在$9$的前面翻倍,所以求出的答案是$1+9*2=19$,但是如果从$7$前面翻倍,那么答案就是$2*7+9=23$,所以刚刚的贪心是错误的
那么要怎么办呢?我们来分析一下式子。
如果用数学式子表示答案的话,那么不加操作$3$答案为$Ans=∑(ans[i])$,那如果我们在$j$处用操作$3$呢?$Ans=∑(ans[i])-a[j-1]+a[j]$,不难发现,我们用一次操作$3$,我们的收益为$ans[j]-ans[j-1]$,所以我们按照该项与前一项的差值进行排序,贪心即可。不算排序的话复杂度为$O(n)$
代码如下:
```
#include<bits/stdc++.h>
using namespace std;
#define re register
#define il inline
#define inf 1234567890
il int read()
{
re int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
#define maxn 50005
#define maxm 505
struct wall
{
int k,p,x;
}e[maxn];
struct lsh
{
int num,map,pax;
}a[maxn<<1];
struct getans
{
int data,num;
}d[maxn];
int n,m,ans[maxn],col,cnt,vis[maxn],Ans,V[maxn],maxx;
il bool cmp(lsh a,lsh b)
{
return a.map<b.map;
}
il bool cmp1(getans a,getans b)
{
return a.data>b.data;
}
int main()
{
n=read(),m=read();
for(re int i=1;i<=n;++i)
{
a[++cnt].map=read(),e[i].p=read(),a[cnt].num=i,a[cnt].pax=0;
}
for(re int i=1;i<=n;++i)
{
a[++cnt].map=read(),a[cnt].num=i,a[cnt].pax=1;
}//离散化,把所有的x值存入map中
sort(a+1,a+cnt+1,cmp);
for(re int i=1;i<=cnt;++i)
{
if(a[i].map!=a[i-1].map)
{
++col;
}
(!a[i].pax?e[a[i].num].k:e[a[i].num].x)=col;
}//去重
Ans=ans[1]=maxx=vis[e[1].k]=e[1].p;//这里要注意,第一个点显然不能被加倍,所以我们要特判一下
for(re int i=2;i<=n;++i)
{
maxx=max(maxx,e[i].p);//操作2实现
vis[e[i].k]+=e[i].p;//操作1实现
ans[i]=max(maxx,vis[e[i].x]);//求出答案,两种方案的较优值
Ans+=ans[i];//先算出所有ans的和
d[i].data=ans[i]-ans[i-1],d[i].num=i;//算出差值
}
sort(d+1,d+n+1,cmp1);
for(re int i=1,j=1;j<=m&&i<=n;++i)
{
if(d[i].data<=0) break;//因为差值排好了序,所以如果一个点与前面一项的差值小于0,则肯定会带来“负面影响”,所以直接break
if(!V[d[i].num]&&!V[d[i].num-1])
{
Ans+=d[i].data;
V[d[i].num]=V[d[i].num-1]=1;//这里注意前后两项都要标记
++j;
}
}
printf("%d",Ans);
return 0;
}
```