https://codeforces.com/contest/1154/problem/F
题意：你现在要买k把铲子，商店有n把铲子，价格数组给出。现在有m个优惠：如果买了x_i个铲子，那么其中y_i个最便宜的铲子免费。一次只能使用一个优惠或者不使用。求最少花费。
C++版本一
题解：完全背包+DP+思维
1、相比传统完全背包，这个问题要先让前i个物品最优；
2、x最为体积，区间[i-x+1,i-x+y]的和作为价值；
3、此题解寻找最大折扣；
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=2000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r;
ll ans,cnt,flag,temp,sum[N];
ll a[N],dp[M],w[N],v[N];
int main()
{
#ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout);
#endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++){scanf("%I64d",&a[i]);}sort(a+1,a+n+1);for(int i=1;i<=m;i++){//scanf("%d%d",&e[i].x,&e[i].y);scanf("%I64d%I64d",&w[i],&v[i]);}for(int i=1;i<=n;i++){sum[i]=sum[i-1]+a[i];}for(int j=1;j<=k;j++){for(int i=1;i<=m;i++){if(j<w[i])continue;dp[j]=max(dp[j],dp[j-w[i]]+sum[j-w[i]+v[i]]-sum[j-w[i]]);}}cout<<sum[k]-dp[k]<<endl;//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif//cout << "Hello world!" << endl;return 0;
}
C++版本二
题解：
1、对折扣规则排序，降低复杂度；
2、前缀和；
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define INF 0x3f3f3f3f;
#define fi first
#define se second
#define MP make_pair
#define PI pair<int,int>
#define lson l,m,rt<<1,ls,rs
#define rson m+1,r,rt<<1|1,ls,rs
#define test printf("here!!!\n")
using namespace std;
const int mx=2e5+10;
int n,m,k;
ll a[mx];
ll qz[mx];
ll dp[mx];
struct Node
{int x;int y;
}b[mx];
bool cmp(const Node &a,const Node &b)
{if (a.x!=b.x) return a.x<b.x;return a.y<b.y;
}
int main()
{memset(dp,0x3f,sizeof(dp));dp[0]=0;scanf("%d%d%d",&n,&m,&k);for (int i=1;i<=n;++i){scanf("%I64d",&a[i]);}for (int i=1;i<=m;++i){scanf("%d%d",&b[i].x,&b[i].y);}sort(a+1,a+n+1);for (int i=1;i<=n;++i){qz[i]=qz[i-1]+a[i];}sort(b+1,b+n+1,cmp);for (int i=1;i<=k;++i){dp[i]=min(dp[i],dp[i-1]+a[i]);for (int j=1;b[j].x<=i;++j){dp[i]=min(dp[i],dp[i-b[j].x]+qz[i]-qz[i-b[j].x+b[j].y]);}}printf("%lld\n",dp[k]);
}