F. Shovels Shop 背包DP

题意:

商店里有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,1,n)
    RI(a[i]);
    sort(a+1,a+1+n);

    rep(i,1,n)
    sum[i]=sum[i-1]+a[i];
    rep(i,1,m)
    RII(v[i],c[i]);

    rep(j,1,k)
    rep(i,1,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 0;
}

View Code

将背包的两个for循环顺序交换一下就会wa ？因为这种顺序是只取只取一个（优惠一次一次只能用一种）为分组背包！

更加简便的题解：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
const int maxn=2e5+10;
const int maxk=2e3+10;

int n,m,k;
int a[maxn],s[maxn];
int g[maxk];
int f[maxk];

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        if(x<=k) g[x]=max(g[x],y);
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=k;i++) s[i]=s[i-1]+a[i];
    for(int i=1;i<=k;i++)
    {
        f[i]=0;
        for(int j=0;j<i;j++)
            f[i]=max(f[i],f[j]+s[j+g[i-j]]-s[j]);
    }
    cout<<s[k]-f[k]<<endl;
}

View Code