洛谷P1048 采药

30分做法

直接枚举加剪枝，最坏复杂度为$O(2^n)$。
$Code:$

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
    int jz,sj;
}a[105];
int ans,m;
void dfs(int t,int v,int n)
{
    if(t>m) {
        ans=max(ans,n);
        return;
    }
    dfs(t+1,v,n);
    if(v-a[t].sj>0) dfs(t+1,v-a[t].sj,n+a[t].jz);
    if(v-a[t].sj==0) {
        ans=max(ans,n+a[t].jz);
        return;
    }
}
int main()
{
    int time;//由于没开#include<ctime>,因此不会CE。
    scanf("%d%d",&time,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a[i].sj,&a[i].jz);
    }
    dfs(1,time,0);
    printf("%d\n",ans);
}

100分做法

前置技能：启发式搜索

我们写一个估价函数f，可以剪掉所有无效的 $0$ 枝条（就是剪去大量无用不选枝条）。
数学上有对此方法的论证，请自行搜索。
这样，最慢的测试点才 $7ms$ ，比刚才的 $>1000ms$ 快多了！
$Code:$

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 105 ;
int n,m,ans;
struct Node{
    int a,b;//a代表时间，b代表价值 
    double f;
}node[N];

bool operator< (Node p,Node q) {
    return p.f>q.f;
}

int f(int t,int v){
    int tot=0;
    for(int i=1;t+i<=n;i++)
        if(v>=node[t+i].a){
            v-=node[t+i].a;
            tot+=node[t+i].b;
        }
        else 
            return (int)(tot+v*node[t+i].f);
    return tot;
}

void work(int t,int p,int v){
    ans=max(ans,v);
    if(t>n) return ;
    if(f(t,p)+v>ans) work(t+1,p,v);
    if(node[t].a<=p) work(t+1,p-node[t].a,v+node[t].b);
}

int main()
{
    scanf("%d %d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&node[i].a,&node[i].b);
        node[i].f=1.0*node[i].b/node[i].a;
    }
    sort(node+1,node+n+1);
    work(1,m,0);
    printf("%d\n",ans);
    return 0;
}