不會做，看了各種題解都不理解后來看這篇看懂了，這篇我覺得是我看的寫的最好的了，關鍵就是最后小矮人跑出去的序列一定是一個身高+臂長遞增的序列（意會一下？），所以按這個排序是為了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;新聞熱點
疑難解答
