题解 P4945 【最后的战役】

Nemlit

2018-10-27 19:36:45

Solution

听说本题正解是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; } ```