题意:
商店里有n把铲子 每个铲子有其标价
一个人要买k吧
有m个优惠政策
每个优惠政策有两个元素x，y
表示 正好买x个铲子的时候 这x个铲子中最便宜的y个铲子免单
求用最少的前买到k个铲子
显然 将n个铲子升序排序好 取前k个 剩下的和本题无关！！
然后前缀和 方便求区间的价值和
要求最少的钱 其实可以转化为求最大的优惠数额
到这一步大致可以看出是一个背包问题了
每个优惠政策可以无限次使用 所以是一个完全背包
即使每次价值都随着容量改变 也可以用背包法来做
#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
#define N 200000+5 int a[N];
ll dp[N];
ll sum[N];
int v[N];
int c[N]; int main()
{
int n,m,k;
RIII(n,m,k);
rep(i,,n)
RI(a[i]);
sort(a+,a++n); rep(i,,n)
sum[i]=sum[i-]+a[i];
rep(i,,m)
RII(v[i],c[i]); rep(j,,k)
rep(i,,m)
if(j>=v[i])
dp[j]=max(dp[j],dp[j-v[i]]+sum[j-v[i]+c[i]]-sum[j-v[i]]);
cout<<sum[k]-dp[k]; return ;
}
将背包的两个for循环顺序交换一下就会wa ？因为这种顺序是只取只取一个 （优惠一次一次只能用一种） 为分组背包！
更加简便的题解：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
const int maxn=2e5+;
const int maxk=2e3+; int n,m,k;
int a[maxn],s[maxn];
int g[maxk];
int f[maxk]; int main()
{
cin>>n>>m>>k;
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=,x,y;i<=m;i++)
{
scanf("%d%d",&x,&y);
if(x<=k) g[x]=max(g[x],y);
}
sort(a+,a+n+);
for(int i=;i<=k;i++) s[i]=s[i-]+a[i];
for(int i=;i<=k;i++)
{
f[i]=;
for(int j=;j<i;j++)
f[i]=max(f[i],f[j]+s[j+g[i-j]]-s[j]);
}
cout<<s[k]-f[k]<<endl;
}