洛谷P4823 拯救小矮人 [TJOI2013] 贪心+dp
正解:贪心+dp
解题报告:
我以前好像碰到过这题的说,,,有可能是做过类似的题qwq?
首先考虑这种显然是dp?就f[i][j]:决策到了地i个人,跑了j个的最大高度,不断更新j的上限就得到答案了(显然i可以省略但为了表述更清晰一点就懒得省辣?
然后这时候就考虑一个问题,就是,dp的要求是无后效性嘛,但这里有个问题,假如有三个人,高度分别为(1,1)(1,1)(100,100),然后洞的深度是100,如果直接按这个顺序dp,那就只有最后一个人能跑出去了,但实际上只要我们合理安排一下顺序他们都能出去的
所以考虑怎么样的顺序是欧克的
那像这样子贪心决定顺序之类的有个很基本的套路,叫微扰法,就直接单独提出两个来然后交换位置看影响嘛
首先显然如果只有一个人能跑出去就都一样儿了,反正是要dp,我们就不care到底怎么排了反正结果是一样的
但是如果两个人都能跑出去,那肯定是逃生能力大的后跑,这里的逃生能力指的是a+b的那个值
综上,通过贪心可得,先对所有人按a+b排序,然后dp一下就好,over!
然后我在重载<的时候把gd和gs打混了,,,然后我过了几万组拍,,,?我也布吉岛我怎么做到的TT
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
const int N=2000+10;
int n,m,f[N],as;
struct node{int a,b;}nod[N];
il int read()
{
rc ch=gc;ri x=0;rb y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il bool operator < (node gd,node gs){return gd.a+gd.b<gs.a+gs.b;}
int main()
{
n=read();rp(i,1,n)nod[i]=(node){read(),read()};m=read();
sort(nod+1,nod+1+n);memset(f,-1,sizeof(f));f[0]=0;rp(i,1,n)f[0]+=nod[i].a;
rp(i,1,n){my(j,as,0)if(f[j]+nod[i].b>=m)f[j+1]=max(f[j+1],f[j]-nod[i].a);if(f[as+1]>=0)++as;}
printf("%d\n",as);
return 0;
}