Shovels Shop

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 DEBUG
	freopen("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 DEBUG
	printf("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]);
}