Luogu P4945 【最后的战役】

本来以为做法一样，就是少带个$log$，结果发现看不懂出题人的题解（我好菜啊）

那就自己写一篇吧

比较简单的$DP$思路

状态定义：

前两个转移很好处理，第三个好像就不好办了

不妨暴力定义进状态里

设$dp[i][j]$表示前$i$秒用了$j$次第三种转移的最大能量和

转移：

三种转移

$(i'<i)$

$1,dp[i][j]=max(dp[i][j],dp[i-1][j]+maxleft{p[i'] ight})$

$2,dp[i][j]=max(dp[i][j],dp[i-1][j]+sum_{k[i']=k[i]}p[i'])$

$3,dp[i][j]=max(dp[i][j],dp[i-2][j-1]+2*max(maxleft{p[i] ight},sum_{k[i']=k[i]}p[i']))$

考虑搞出来这两个东西

$1,maxleft{p[i'] ight}$

前缀最大值即可$O(1)$

$2,sum_{k[i']=k[i]}p[i']$

我写的离散化然后每次用就是$O(1)$

$map$也可以，但是用$map$的话，切记，对于相同的$i$，上式的值是相同的，不要放到枚举$j$的内层循环了

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=50010;
int dp[maxn][510],n,m,k[maxn],p[maxn],x[maxn],mp[2*maxn],maxa,cnt,sum[2*maxn];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&k[i],&p[i]);
        mp[++cnt]=k[i];
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&x[i]),mp[++cnt]=x[i];
    sort(mp+1,mp+cnt+1);
    cnt=unique(mp+1,mp+cnt+1)-mp-1;
    for(int i=1;i<=n;i++)
    {
        k[i]=lower_bound(mp+1,mp+cnt+1,k[i])-mp;
        x[i]=lower_bound(mp+1,mp+cnt+1,x[i])-mp;
    }
    for(int i=1;i<=n;i++)
    {
        maxa=max(maxa,p[i]),sum[k[i]]+=p[i];
        int tmp=max(maxa,sum[x[i]]);
        for(int j=0;j<=min(i,m);j++)
        {
            if(i>1&&j)
                dp[i][j]=max(dp[i][j],dp[i-2][j-1]+2*tmp);
            dp[i][j]=max(dp[i][j],dp[i-1][j]+tmp);
        }
    }
    int ans=0;
    for(int i=0;i<=m;i++)
        ans=max(ans,dp[n][i]);
    printf("%d
",ans);
    return 0;
}