題解

這么明顯的一個(gè)dp，我怎么就沒看出來(lái)呢？！
首先我們需要一些前提條件：任何劃分出來(lái)的一個(gè)區(qū)間的長(zhǎng)度不應(yīng)該超過(guò)c。
如果這個(gè)區(qū)間長(zhǎng)度大于c，那么設(shè)len=n?c+klen=n?c+k，那么這個(gè)區(qū)間應(yīng)該被分成n個(gè)長(zhǎng)度為c的區(qū)間和一個(gè)長(zhǎng)度為k的區(qū)間，因?yàn)檫@樣的話去掉的元素?cái)?shù)量是相同的，并且區(qū)間更小有利于較小的值不易被取到。因?yàn)槊看稳サ舻淖钚≈祪H僅是局部最小值，不一定是全局最小值。大區(qū)間就不一樣了，雖然大區(qū)間去掉的元素?cái)?shù)量相同，但是這些元素會(huì)更小一些。
這樣的話，我們劃分出來(lái)的區(qū)間應(yīng)該盡量使得區(qū)間的長(zhǎng)度為c。
然后我們使用dp來(lái)解決剩下的部分：
dp[i]dp[i]表示前i個(gè)元素組成的集合對(duì)應(yīng)的答案。
狀態(tài)轉(zhuǎn)移方程：
策略：第i個(gè)是否與前c-1個(gè)構(gòu)成一個(gè)長(zhǎng)為c的區(qū)間。
dp[i]=min(dp[i?1]+a[i],dp[i?c+1]+sum[i]?sum[i?c]+min[i?c+1,i])dp[i]=min(dp[i?1]+a[i],dp[i?c+1]+sum[i]?sum[i?c]+min[i?c+1,i])
由于用到了min[i?c+1,i]min[i?c+1,i]我們還需要維護(hù)一個(gè)最近cc<script type="math/tex" id="MathJax-Element-339">c</script>個(gè)a元素的最小值，方便起見，直接使用multiset即可。

反思

以后遇到這種序列題目，找出一些必要條件之后一定往dp上多想一想。

---

代碼

#include <cstdio> #include <set> using namespace std; typedef long long ll; const int maxn = 100007; int a[maxn],n,c; ll dp[maxn],sum[maxn]; multiset<int> st; int main(){scanf("%d%d",&n,&c);for(int i = 1;i <= n;++i){scanf("%d",&a[i]);dp[i] = sum[i] = sum[i-1] + a[i];}for(int i = 1;i < c;++i)st.insert(a[i]);for(int i = c;i <= n;++i){st.insert(a[i]);dp[i] = min(dp[i-1] + a[i],dp[i-c] + sum[i] - sum[i-c] - *st.begin());st.erase(st.find(a[i-c+1]));}printf("%lld\n",dp[n]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的codeforces 940E Cashback 有趣的dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。