题解 | #小竹与妈妈#

C小竹关禁闭
大佬都是从前面开始dp的，只有我傻傻的从后面开始dp。
这里定义一个三维的状态（反正不会爆空间）
f[i][j][k]
表示第i个物品，j是选不选i，k是后面m（也就是k）个位置中选还是不选 然后就是丑陋的代码

cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=n;i>=1;i--) {
        for(int j=n;j>i;j--) {
            //这个物品选,那后面的只能不选
            if(j-i>m)f[i][1][1]=max({f[i][1][1],f[j][1][1],f[j][0][0],f[j][0][1]});
            else f[i][1][1]=max({f[i][1][1],f[j][0][0]});
            
            //这个物品不选，但是后面m个里面也不选
            if(j-i>m)f[i][0][0]=max({f[i][0][0],f[j][1][1],f[j][0][0],f[j][0][1]});
            else f[i][0][0]=max({f[i][0][0],f[j][0][0]});
            
            //这个物品不选，但是后面m个里面选
            if(j-i>m)f[i][0][1]=max({f[i][0][1],f[j][1][1],f[j][0][0],f[j][0][1]});
            else f[i][0][1]=max({f[i][0][1],f[j][1][1],f[j][0][1]});
        }
        f[i][1][1]+=a[i];//最后选的要加上自己
    }
    cout<<max({f[1][1][1],f[1][0][1],f[1][0][0]});