1252. 天平

题目描述

J有一架用来称牛的体重的天平。与之配套的是N(1<=N<=40)个已知质量的砝码（所有砝码质量的数值都在31位二进制内）。每次称牛时，他都把某头奶牛安置在天平的某一边，然后往天平另一边加砝码，直到天平平衡，于是此时砝码的总质量就是牛的质量（FJ不能把砝码放到奶牛的那边，因为奶牛不喜欢称体重，每当FJ把砝码放到她的蹄子底下，她就会尝试把砝码踢到FJ脸上）。天平能承受的物体的质量不是无限的，当天平某一边物体的质量大于C(1<=C<2^30)时，天平就会被损坏。 砝码按照它们质量的大小被排成一行。并且，这一行中从第3个砝码开始，每个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和。 FJ想知道，用他所拥有的这些砝码以及这架天平，能称出的质量最大是多少。由于天平的最大承重能力为C，他不能把所有砝码都放到天平上。 现在FJ告诉你每个砝码的质量，以及天平能承受的最大质量。你的任务是选出一些砝码，使它们的质量和在不压坏天平的前提下是所有组合中最大的。

题目分析

这一道题用暴力递归就是枚举每一个数选或不选，那时间复杂度就是的 2n 太慢了！ 我们先看一看这些砝码的特点：一个砝码将大于前两个砝码的和。 则： w[3]-w[2]>=w[1] w[4]-w[3]>=w[2] …… w[i]-w[i-1]>=w[i-2] 把所有的式子加起来则可以得到： w[i]-w[2]>=前i-2个数的和； 我们其实可以分析以下三种情况： w[n]+w[n−1]<=c ： 如果我们选择前n-1个数的和，那和一定是小于w[n-1]+w[n]的，所以我们一定要选w[n]。 w[n]<=c<w[n]+w[n−1] ： 我们不能同时选w[n]+w[n-1]但如果我们选前n-2个数的和，一定是小于w[n]的，而选n-1个数，则有可能大于w[n]，所以我们要选第n个砝码或第n-1个砝码。 c<w[n] ： 我们不能选择第n个砝码。 这个时候我们便可以用递归做这一道题，假如是情况一，我们用暂存的和把它加起来就行了。如果是情况三，我们不加，然后边把参数-1（因为第n个数已经没有用了），递归下去。 如果是情况二，我们就两个都递归一下，然后把参数-2。 最坏的情况是一直都是情况2，时间复杂度为 2n2

代码

#include<cstdio> #include<cstring> #include<cstdlib> using namespace std; long long a[45]; int b[51]; long long ans=0,sum=0; int cmp(const void *xx,const void *yy) { long long n1=*(long long *)xx; long long n2=*(long long *)yy; if(n1>n2) return 1; else return -1; } int n;long long c; void dfs(int s) { if(s==0) { if(sum<=c&&sum>ans) { ans=sum; } return ; } else { if(c-sum>=a[s]+a[s-1]) { sum+=a[s]; dfs(s-1); sum-=a[s]; } else if(c-sum<a[s]) { dfs(s-1); } else { sum+=a[s]; dfs(s-2); sum-=a[s]; sum+=a[s-1]; dfs(s-2); sum-=a[s-1]; } } } int main() { scanf("%d",&n); scanf("%lld",&c); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } qsort(a+1,n,sizeof(long long),cmp); dfs(n); printf("%lld\n",ans); return 0; }