【GDOI2017模拟8.11】选择

之前漏了一天的blog，补上。

Description

有n中物品，每种物品有无限个，第i种物品的单价为ai。 问从中选出k个物品的价格有多少种，以及这些钱数。 n,k,ai<=500

Solution

首先，可以有一个很显然的DP模型。 设F[i][j][k]表示前i个物品，选了j个，能不能达成和为k。 转移显然，但是状态有N^4个，会炸。 怎么办呢？我们肯定要优化掉一维。i和k显然无法优化，我们思考一下如何优化j。 我们先把所有的ai减去min(ai)（一下简称min）。 我们再设F[i][k]表示前i个物品，达成和为k最少需要买几个物品。 如果买了x个，和为sum，那么真实的和就是sum+k*min。 因为这x个的实际价格都要多min，加上x*min，剩下的k-x个相当于买min，加上(k-x)*min. 然后就可以O(N^3)来做了。

Code

#include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define N 505 using namespace std; int n,k,f[N*N],a[N]; int main() { scanf("%d%d",&n,&k);int mi=0x7fffffff,mx=0; fo(i,1,n) scanf("%d",&a[i]),mi=min(mi,a[i]),mx=max(mx,a[i]); memset(f,127,sizeof(f));f[0]=0; fo(i,1,n) { a[i]-=mi;if (!a[i]) continue; fo(j,a[i],k*(mx-mi)) f[j]=min(f[j],f[j-a[i]]+1); } fo(i,0,k*(mx-mi)) if (f[i]<=k) printf("%d ",i+mi*k); }