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]);
}