不会做，看了各种题解都不理解后来看这篇看懂了，这篇我觉得是我看的写的最好的了，关键就是最后小矮人跑出去的序列一定是一个身高+臂长递增的序列（意会一下？），所以按这个排序是为了DP，然后设f[i]为出去i个人后剩下人的最大高度DP
#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long long#define lowbit(x) x&(-x)using namespace std;void up(int &x,int y){if(x<y)x=y;}void down(int &x,int y){if(x>y)x=y;}const int maxn = 2100;struct node{ int a,b;}a[maxn];int n,H;bool cmp(node x,node y){return x.a+x.b<y.a+y.b;}int f[maxn];int main(){ scanf("%d",&n); int sum=0; for(int i=1;i<=n;i++) scanf("%d%d",&a[i].a,&a[i].b),sum+=a[i].a; scanf("%d",&H); sort(a+1,a+n+1,cmp); memset(f,-1,sizeof f); f[0]=sum; for(int i=1;i<=n;i++) { for(int j=n;j>=1;j--) if(f[j-1]!=-1&&f[j-1]+a[i].b>=H) up(f[j],f[j-1]-a[i].a); } int ans; for(ans=1;ans<=n;ans++) if(f[ans]==-1) break; PRintf("%d/n",ans-1); return 0;}新闻热点
疑难解答
