BZOJ3174: Tjoi2013 拯救小矮人

本文主要是介绍BZOJ3174: Tjoi2013 拯救小矮人，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：
先贪心一发，逃生能力(a+b)强的肯定是放在最后走，然后dp;f[i]表示走了i以后的剩下的最大高度。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
const int imax=2000+229; 
int n,H;
struct Node{ int a,b;bool operator < (const Node &rhs) const{return a+b<(rhs.a+rhs.b);    }
}t[imax];
int f[imax];void iread()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d%d",&t[i].a,&t[i].b);sort(t+1,t+n+1); scanf("%d",&H);
}void iwork()
{int ans=0;memset(f,-1,sizeof(f));f[0]=0;for(int i=1;i<=n;i++) f[0]+=t[i].a; for(int i=1;i<=n;i++)for(int j=n;j>=0;j--)if(f[j]+t[i].b>=H)f[j+1]=max(f[j+1],f[j]-t[i].a); for(int i=n;i>=0;i--) if(f[i]>=0) { ans=i; break;}printf("%d\n",ans);
}int main()
{iread();iwork();return 0;
}

这篇关于BZOJ3174: Tjoi2013 拯救小矮人的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---