Cashback (DP 区间最小值)

2018-04-18

Cashback

题意

输入n和c。接下来给出长度为n的数组A。你可以将数组A划分成任意个子数组，假设其中一个子数组的长度为k，那么可以减去这个子数组内前k/c个（向下取整）小的数。要使划分后数组内的元素和最小，问最小的和为多少？

思路

预感到是DP，但是没有什么L用……

分析一下：如果其中一个子数组的长度k< c，那么这个数组就一个也不能减少；如果长度k=c，那么就刚好减少一个；如果长度在c< k< 2c之间，并没有任何贡献，还是只能少一个。也就是说，长度正好为c的数组是优秀的。那么长度为2c的数组呢？我们假设[0,c-1]内，最小的数字为min1，第二小的是min2，[c,2c-1]内，最小的数字为min3，那么，如果min2< min3，对于划分（2个长度为c）来说，消去的数字是min1+min3，而对于划分（1个长度为2c），消去的数字就是min1+min2，显然是两个c长度的划算。如果min2>=min3，对于划分成（2个长度为c）来说，消去的数字就是min1+min3，对于划分（一个长度为2c），消去的数字为min1+min3，两者是相等的。因此综上而言，将数组划分成长度为c的小数组更划算一些。

那么就用到dp了，dp[i]指前i个数字的最小和。

对于一个数字a[i]来说，（i>c）dp[i] 要么是接受前一个数字的dp再加上自己的大小，要么就是重新进入一个长度是c的数组，起始index为i-c+1，dp[i]=dp[i-c] (前i-c的最小和）+sum[i]-sum[i-c] （这一段新的长度为c的数组的总和）- min{a[i-c+1], … , a[i] }（这一段长度是c的区间里的最小值），即：

dp[i] = min(dp[i-1]+a[i] , dp[i-c] + sum[i] - sum[i-c] - min{a[i-c+1], … , a[i] } )

对于区间最小值min，用一个multiset维护就好了。multiset里只放当前i为最后一个数字的c个数字。而multiset中的.begin() 会返回容器中最小的数的指针。如果去掉最前面一个放进来的数字呢？. erase( .find(a[i-c+1]))就好了。

看！代码

#include<bits/stdc++.h>
using namespace std;
const int MAX=100010;
int n,c;
long long dp[MAX],a[MAX]; //dp[i]指前i个元素相加的最小和
long long sum[MAX]; //前i个元素和
multiset<long long>s; //s用来维护长度为c的区间内的最小值
int main()
{
	scanf("%d%d",&n,&c);
	sum[0]=0;
	for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
		dp[i]=sum[i]=sum[i-1]+a[i]; 
		//初始化dp值，显然长度不足c的dp值为前i个数之和，其他的默认初始值为前i个数之和
    }
    for(int i=1;i<c;i++)
        s.insert(a[i]);
    for(int i=c;i<=n;i++)
    {
        s.insert(a[i]);
        dp[i]=min(dp[i-1]+a[i],dp[i-c]+sum[i]-sum[i-c]-*s.begin());
        //前一个数加上自己的和，前一个c区间及之前的最小和加上这个新的c区间的总和，减去这个区间的最小值
        s.erase(s.find(a[i-c+1]));//删去下一步到了区间外的数字
    }
	printf("%lld",dp[n]);
	return 0;
}