链接

题意

        给你n个点，每个点有个权值a[i]，可以在n个点中选x个特殊点，要保证最后的序列中每连续k个点都至少有一个特殊点，问x个特殊点的权值和最大可以是多少
        1<=k,x<=n<=200
        1<=k,x<=n<=200

题解

        dp[i][j]前i个点选j个特殊点，且第j个点在位置i
        dp[i][j]=max(dp[ii][j-1]) i-ii-1<=k

链接

题意

        给你n个点，每个点有个权值a[i]，可以在n个点中选x个特殊点，要保证最后的序列中每连续k个点都至少有一个特殊点，问x个特殊点的权值和最大可以是多少
        1<=k,x<=n<=5000
        1<=k,x<=n<=5000

题解

        dp[i][j]前i个点选j个特殊点，且第j个点在位置i
        dp[i][j]=max(dp[ii][j-1]) i-ii-1<=k
        先不管j，维护一个i单调增，dp值单调减的队列即可。

链接

题意

        给一个序列，让你构造一个相等长度的序列，构造的序列中每个元素的取值范围都为[1,5]。
        构造要求：
        1. 若原序列a[i]==a[i+1]，那么构造的序列b[i]!=b[i+1]；
        2. 若原序列a[i]>a[i+1]，那么构造的序列b[i]>b[i+1]；
        3. 若原序列a[i]<a[i+1]，那么构造的序列b[i]<b[i+1]；
        若答案存在，输出任意一个，否则输出-1。
        (1≤𝑛≤105)

题解

        开一个dp[N][5]，填完了前i位且第i位是k的方案是否可行

链接

题意

        给你一个n( (1≤𝑛≤100000)个数的数列，让你构造一个序列，保证每个位置的数字能整除这个位置的下标。问有多少个子序列满足这种做法。

题解

        dp[i][j]代表前i个数，构成长度为j的数列的方案数
        dp[i][j] <--- dp[i-1][j-1]  j|a[i] 预处理每个数的因子即可
        然后发现若从大到小枚举因子则第一维可以优化掉，

链接

题意

        给你一棵树，在树中找出一条路径（也可以只有一个点），让这条路径(点权和-边权和)最大。
        树的节点最多3e5，权值最大1e9

题解

        随便找个节点当根，dp1[i]代表以i为根的子树上，经过i点，走向子树的路径的最大权值，dp2[i]为次大。得到此数组之后，定义路径的深度节点为路径上的所有节点中，深度最小的那个节点，枚举每个节点作为深度节点的时候的最大权值路径，如果dp2<0则取dp1,否则取dp1+dp2转移

链接

题意

        给你一个最多16行1e4列的矩阵A，对矩阵按列优先遍历，得到一维数组B，当然，此时也可以输A是B按列优先访问得到的二维数组，定义一维数组的权为任意相邻两个数的差的绝对值的值小值，你可以对A进行行互换，但不可列互换，问换完之后，对矩阵按列优先遍历之后的B的权的最大值是多少。

题解

        分析发现与列数量无关，再分析，发现行互换，相当于在对行重排列，再分析发现这其实是一个Hamiltonpath。枚举起点和终点即可。

链接

题意

        给你n个数，分成k组，允许某些数不放，要求每组内最大值与最小值的差值不超过5。求k组最多可以放多少个数。

题解

        排序后预处理每个数向左延伸的最远位置,l[i]
        设：
        dp[i][j] 前i个数分j组最多能放多少个数 
        dp[i][j]=max(dp[i−1][j],dp[i][j−1],dp[l[i]−1][j−1]+i−l[i]+1)

链接

题意

        给你长度为n的01串,最多把k个0变成1,变完后连续的最长的全是1的串的长度是多少,并且输出最后得串;
        k<n<3e5

题解

        暴力:
            dp[i][j]代表前i个数把j个0变成1后,以位置i结尾的全为1的串长度最大是多少
            不妨设串为s[1:n]
            if s[i] = 0
                dp[i][j]   <----  dp[i-1][j-1]+1
            if s[i] = 1
                dp[i][j]   <----  dp[i-1][j]+1
        解法1:
            套路，统计前缀0的个数，然后枚举每一个位置作为变完后的全为1的串的结尾，于是起点就可以二分了，
            枚举终点i，则sum[i]-sum[j]<=k,sum具有单调性，于是二分
        解法2(优化):
            定义终点i对应的起点j为: 
                j=f(i)
            f单调
            可以用双指针扫描达到线性复杂度

链接

题意

        要n点药水,目前每秒钟增加x点药水,拥有k点魔法的你有两种方案提前增加效率：
        一：把每秒产生的药水数量变为ai，消耗魔法值 bi；
        二：瞬间产生ci点药水，不消耗时间，但是需要魔法值di。
        输入的ci，di 非减。
        第一种魔法你最多只能用一次
        第二种魔法你最多也只能用一次

题解

        枚举第一种魔法，二分第二种魔法

链接

题意

        共有n个人，编号为1~n。他们每个人属于且仅属于R阵营或N阵营中的一个。现在他们要进行一场投票。投票可能进行多轮，每一轮投票都是按照从1~n的顺序，当轮到某一人投票的时候，他可以什么都不做，也可以随便挑选一人使他丧失投票的权利。每个人都会代表自己阵营的利益。一个人如果丧失了投票权利，则他直到这场投票结束都不能再投票。投票直到某一阵营一个人都没有的时候就会结束，此时一个人都没有的阵营失败，另一个阵营获胜。
        
        现在给定每个人所属的阵营，问最后哪个阵营会获胜。
        要求线性时间解决

题解

        贪心做法:
            每个人干掉他后面的第一个非本阵营的人即可，模拟一下