CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
===== C =====

显然先把怪打到如果后面那个人爆炸他也会被炸死是必须操作的一步。

然后就是会循环炸死，那么找到一个剩下血量最少的打死即可。

===== D =====

这个题，懒得讲了，就把完全图画出来，然后贪心的在这个完全图上走

只要能走小的就走小的

大概就是1-2，2-1，1-3，3-2(因为此时再走1的话，1就走不了)推一推就推出来了

===== E =====

这个题很巧妙就巧妙在，路径长度为当前点的某个性质-上一个点的某个性质，

如果要求a到b的最短路，如果b是a的倍数或者a是b的倍数，最后答案就是|b的性质-a的性质|，和中间路径无关。

如果b是a的倍数，反过来同理

那么方案数就是从a一直乘质数乘到b的方法数，方案数显然就说所有质约数的排列数，注意是有重的

如果b不是a的倍数， 直觉来看是走到a和b的gcd，然后再走最短，方法同理~

===== F =====

**线段树优化DP！！！**

直观来看可以dp i,j 表示第一个串匹配到第i位，第2个串匹配了前j位的最小值

转移分了三种

1）如果$a_i<b_j$,那么贪心的思想是没必要删的$dp[i][j] =max(dp[i][j],dp[i-1][j])$

但是如果有$p_i$小于等于0，则有$dp[i][j] =max(dp[i][j],dp[i-1][j]+p_i)$

2）如果$a_i=b_j$,那么匹配上了$dp[i][j+1] =max(dp[i][j+1],dp[i-1][j])$

3）如果$a_i>b_j$，那必删，$dp[i][j+1] =max(dp[i][j+1],dp[i-1][j]+p_i)$

对于情况1和3来说，由于**b是单调的**，覆盖的都是一段区间，可以直接区间进行操作，

又因为b是单调递增的，所以情况2只会出现一次，单次修改即可。

因此建一颗长度为m的线段树即可。
CVBB ACM Team

用户工具

站点工具

页面工具
