线性dp——1197D

心已赠人 2023-10-12 08:19 59阅读 0赞

一开始没有什么头绪，后来注意到m<=10,考虑是否可以用dp\[i\]\[j\]表示第i位，前面跟了j个数的最大值

那么第i+1个数，直接和第i个数的\[0,m\]的m+1种状态去转移即可，如果是由0或m状态拓展出去的，那么值要-k

策略和序列最大连续子段和的贪心策略一样

#include<bits/stdc++.h>
    using namespace std;
    #define N 300005
    #define ll long long 
    #define INF 0x3f3f3f3f3f3f3f3f
    ll dp[N][15],n,a[N],m,k;
    
    int main(){
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        for(int i=0;i<=n;i++)
            for(int j=0;j<=m;j++)
                dp[i][j]=-INF;
                
        long long ans=0;
        dp[0][0]=0;
        for(int i=0;i<n;i++){
            dp[i+1][0]=0;
            for(int j=0;j<=m;j++)if(dp[i][j]!=-INF){
                if(j==0)
                    dp[i+1][1]=max(dp[i+1][1],dp[i][j]+a[i+1]-k);
                else if(j!=m)
                    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+a[i+1]);
                else dp[i+1][1]=max(dp[i+1][1],dp[i][j]+a[i+1]-k);
                ans=max(ans,dp[i+1][j+1]);
                ans=max(ans,dp[i+1][1]);
            }
        }
        cout<<ans<<endl;
    }

转载于:https://www.cnblogs.com/zsben991126/p/11433974.html

发表评论取消回复

表情：

评论列表（有 0 条评论，59人围观）

还没有评论，来说两句吧...

相关阅读

相关多维线性DP

多维线性DP [72. 编辑距离][72.] 给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。你可以

绝地灬酷狼/ 2024年04月03日 11:09/ 0 赞/ 72 阅读

相关【线性DP】猴子与香蕉

可恶，就差一点就能独立写出这道题了！ [4548. 猴子和香蕉 - AcWing题库][4548. _ - AcWing] 题意： ![bee1bfbae5e15a76a

我就是我/ 2024年03月26日 16:39/ 0 赞/ 91 阅读

相关线性dp——1197D

一开始没有什么头绪，后来注意到m<=10,考虑是否可以用dp\[i\]\[j\]表示第i位，前面跟了j个数的最大值那么第i+1个数，直接和第i个数的\[0,m\]的m+1种

心已赠人/ 2023年10月12日 08:19/ 0 赞/ 60 阅读

相关建模+线性dp——cf1201D

这类题目要首先把模型建立起来，挑选一个好的状态能让dp方程简化很多 / dp[i][0]表示从右到左，最后停在左端 dp[i][1]表示从左到右，最后停在右端 dp

桃扇骨/ 2023年10月11日 09:09/ 0 赞/ 14 阅读

相关 HDU 6739-Invoker【线性DP】

Invoker Time Limit: 15000/12000 MS (Java/Others) Memory Limit: 131072/131072 K (Ja

深碍√TFBOYSˉ_/ 2023年08月17日 16:40/ 0 赞/ 68 阅读

相关【CF1197D】Yet Another Subarray Problem

Description [【CF1197D】Yet Another Subarray Problem][CF1197D_Yet Another Subarray Prob

阳光穿透心脏的1/2处/ 2023年06月05日 08:54/ 0 赞/ 53 阅读

相关 Codeforces Round #637 (Div. 2) D. Nastya and Scoreboard 线性DP

题目链接：http://codeforces.com/contest/1341/problem/D 题意：0~9的数字是由图中的木棒组成的，现在给你若干个显示屏，你可以恰

灰太狼/ 2023年05月21日 07:15/ 0 赞/ 63 阅读

相关 D - WuKong（Floyd+dp）

题目描述： Liyuan wanted to rewrite the famous book “Journey to the West” (“Xi You Ji” in

向右看齐/ 2022年04月23日 11:52/ 0 赞/ 144 阅读

相关线性dp题型总结

LIS问题最长上升子序列 [poj-Longest Ordered Subsequence][] 状态方程 include <cstdio>

缺乏、安全感/ 2022年03月01日 02:52/ 0 赞/ 228 阅读

相关线性dp——cf1096D

dp\[i\]\[j\]表示到第i位，与hard的匹配状态到达了第j位每位有两种决策：消或者不消分别转移一下即可转移代码 for(register int

忘是亡心i/ 2021年11月19日 15:06/ 0 赞/ 289 阅读