题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=5887
一开始想 100个物品 ，而且是随机的，分布均匀那么总的状态数不会太多吧
就像用map试一下，结果MLE
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int INF=1e9;
typedef long long LL;
//LL d[100000];
//d[j] j时间状态下最多多少价值
map<int,int> d,nd;
int main()
{int H,T,t,s,j;map<int,int>::iterator it; while(scanf("%d%d",&H,&T)!=EOF){d.clear();d[0]=0;for(int i=0;i<H;i++){scanf("%d%d",&t,&s);if(t>T) continue;nd[0]=0;for(it=d.begin();it!=d.end();++it){nd[it->first]=max(nd[it->first],d[it->first]);if(it->first+t<=T) nd[it->first+t]=max(d.count(it->first+t)?d[it->first+t]:0,d.count(it->first)?d[it->first]+s:s);}d.swap(nd);nd.clear();}cout<<(--d.end())->second<<endl;}return 0;
}对于DFS搜索时，要加一个估价函数，预计最多能得到的总分数
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
struct Herb{LL time,score;double r;Herb(LL t=1,LL s=0):time(t),score(s){r=(double)s/t;}bool operator < (const Herb& h) const {return r>h.r;}
};
Herb herb[100+5];
LL ans,Last,H,T; int k;
bool h(int i,LL time,LL score){ //估价函数 h()>h*() for(int j=i;j<k&&time<T;j++){if(time+herb[j].time<=T) time+=herb[j].time,score+=herb[j].score;else score+=herb[j].r*(T-time),time=T;}return score>ans;
}
void DFS(int cur,LL time,LL score)
{ans=max(score,ans);if(cur<k&&h(cur,time,score)){if(time+herb[cur].time<=T) DFS(cur+1,time+herb[cur].time,score+herb[cur].score); //拿 DFS(cur+1,time,score); //不拿 }
}
int main()
{LL t,s; while(scanf("%I64d%I64d",&H,&T)!=EOF){k=ans=0;for(int i=0;i<H;i++){scanf("%I64d%I64d",&t,&s);if(t>T) continue;herb[k++]=Herb{t,s};}sort(herb,herb+k);DFS(0,0,0);cout<<ans<<endl;}return 0;
}