题目:http://codeforces.com/contest/1154/problem/F
题意：给你n个商品，然后还有m个特价活动，你买满x件就把你当前的x件中最便宜的y件价格免费，问你买k件花最少的钱是多少
思路：首先这个特价活动就像点外卖一样满多少减多少，你可以分几次来使用同一个优惠或者不同的优惠，然后我们我们分析三个点
1，那个特价活动中x>k的我们肯定都不会使用，因为那个时候已经买满了k件
2，我们肯定是买最便宜的k件来使用特价活动
3，我们其实可以当成分开几组来使用优惠，就像外卖有些时候要分几次来点才划得来一样
那么我们的思路就有了，我们dp[i]代表的是前i个物品的最高优惠价格，我们枚举最后一次使用特价活动是在哪个时候
为了方便我们用几个数组分别记录一些东西
s[i] 代表前i个的总花费
g[i] 代表买满i个最多能减少多少个物品值 （因为活动可能有重复，买i个减x个和y个，这个时候要取最优的情况）
dp[i] 代表的是前i个物品的最高优惠价格
我们枚举最后一次使用活动要枚举边界在哪，所以我们要使用二重循环枚举
这样转化一下，其实和我之前写的一篇数组分组是一样的思路了，主要还是要学会转化，建模
#include<bits/stdc++.h>
#define mod 1000007
#define maxn 200001
using namespace std;
typedef long long ll;
ll n,m,k;
ll dp[maxn];
ll s[maxn];
ll g[maxn];
ll a[maxn];
int main(){
cin>>n>>m>>k;
for(int i=;i<=n;i++) cin>>a[i];
sort(a+,a+n+);
for(int i=;i<=k;i++){
s[i]=s[i-]+a[i];//记录前缀和
}
for(int i=;i<=m;i++){
ll x,y;
cin>>x>>y;
if(x>k) continue;
g[x]=max(g[x],y); //保留特价活动的最优减少数
}
for(int i=;i<=k;i++){ //由前推后
for(int j=;j<i;j++){//枚举最后一次的特价活动位置
dp[i]=max(dp[i],dp[j]+s[j+g[i-j]]-s[j]);
}
}
cout<<s[k]-dp[k];
}