题意：给定商店中的物品数量n和整数d，并给出n个物品的价值。（每个物品有且只有1件）如果满足手上的若干物品价值和+d>=商店中的若干物品和，你可以拿这些物品换下商店里的这些物品。（交换的物品数量不限）且初始状态为你没有任何物品但是你可以空手去换。求能得到的最大价值和在得到最优解的情况下的最小交换次数。题目下面有样例解释，应该可以理解。
首先……每个物品只有一件，但是交换的时候的物品数量却是没有限制的。如果也限制成一件的话贪心即可。
注意到只有一件可以考虑预处理出所有能取到的价值。用01背包跑一遍即可。
然后？这样以后么就可以每次对ans增加d，在ans+d到ans+1的范围内尽量选取更大的并且这个价值能得到的拿。
贪心证明么……如果你拿了更小的值，下次再拿的时候花费的次数肯定相对多了。而能拿的价值是不会变的。所以拿更大的更优。
然后如果在当前阶段ans+d到ans+1都不能拿了说明已经不能继续操作了……那么ans就是最后的最大价值，最小交换次数每增加d就随之自增即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#include<cstdlib>
#define ll long long
#define maxn 1000010
#define inf 1000000000
#define linf (1LL<<50)
using namespace std;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
return x*f;
}
inline void read(char *s,int &ts)
{
char x=getchar();
while(!(x>='a'&&x<='z'))x=getchar();
while(x>='a'&&x<='z')s[++ts]=x,x=getchar();
}
int n,d;
int f[maxn];
int c[maxn];
int main()
{
int sum=0;
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++)
{
scanf("%d",&c[i]);
sum+=c[i];
}
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=sum-c[i];j>=0;j--)
if(f[j]) f[j+c[i]]=1;
int ans=0;
int tot=0;
for(;;)
{
int j;
for(j=ans+d;j>ans;j--)
if(j<=sum&&f[j]) break;
if(ans==j) break;
ans=j;
tot++;
}
printf("%d %d\n",ans,tot);
return 0;
}
评论 (0)
