首页 > 代码库 > TYVJ1305

TYVJ1305

2024-07-19 06:42:04   221人阅读

题解上说这是DP+单调队列优化，我觉得这已经不算是DP了，只算是练习单调队列吧。
设dp[i]表示以a[i]结尾的不超过m个的最大的子段和
dp[i] = max(sum[i]-sum[i-k])1<=k<=m;　　　　　　　　
因为sum[i]是不变的，所以稍微有点数学知识就可以得到
dp[i] = sum - min(sum[i-k]);
这就转换为求i-m到i中sum的最小值了
最后遍历dp取最大值就是答案了，时间复杂度O(n)空间O(n);

 

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define INF 0x3f3f3f3f 6 using namespace std; 7 const int maxn = 300005; 8 struct QUEUE 9 {10     int value;11     int index;12 }que[maxn];13 int a[maxn],sum[maxn],dp[maxn];14 int main()15 {16    // freopen("in.txt","r",stdin);17     int n,m,f,r;18     while(cin>>n>>m)19     {20         sum[0] = 0;21         for(int i = 1;i<=n;++i)22         {23             scanf("%d",&a[i]);24             sum[i] = sum[i-1]+a[i];25         }26         f = 1;r = 1;27         que[1].value = http://www.mamicode.com/0;28         que[1].index = 0;29         for(int i = 1;i<=n;++i)30         {31             dp[i] = sum[i]-que[f].value;32             while(f<=r && que[r].value>=sum[i])r--;33             que[++r].value =http://www.mamicode.com/ sum[i];34             que[r].index = i;35             if(que[f].index<=i-m)f++;36         }37         int ans = -INF;38         for(int i = 1;i<=n;++i)39             ans = max(ans,dp[i]);40         printf("%d\n",ans);41 42     }43     return 0;44 }

 

TYVJ1305


联系
我们