搜索优化能过吗

TempestJueMu @ 2022-07-09 08:37:20

int n,m;
struct node
{
    int v,w,q;
}a[70];
int lst[65];//后缀和
int ans;
bool buy[65];
inline void dfs(int now,int hv,int ls)
{
    if(hv+lst[now]<=ans)return;
    if(now==m+1){ans=max(ans,hv);return;}
    if(ls>=a[now].v&&(a[now].q==0||buy[a[now].q]))buy[now]=1,dfs(now+1,hv+a[now].w,ls-a[now].v),buy[now]=0;
    dfs(now+1,hv,ls);
}
int main()
{
    n=read(),m=read();n/=10;
    for(register int i=1;i<=m;++i)
        a[i].v=read(),a[i].w=read(),a[i].q=read(),a[i].v/=10,a[i].w=a[i].w*a[i].v;
    for(register int i=m;i>=1;--i)lst[i]=lst[i+1]+a[i].w;
    dfs(1,0,n);
    printf("%d",ans*10);
    return 0;
}

by metaphysis @ 2022-07-09 17:45:47

@Guolar_JueMu

这要看数据强度，对于本题来说，很难，毕竟深度优先搜索的时间复杂度是 \text{O}(2^n)，而且在本题环境下似乎并无特别的剪枝措施。

by TempestJueMu @ 2022-07-09 18:36:50

@metaphysis thx

by j_steady @ 2022-08-05 18:46:01

@metaphysis 不能记忆化吗 qwq

by metaphysis @ 2022-08-06 10:03:42

@j_steady

对于典型的01背包问题，即使使用记忆化，当 n 较大时也不可行（例如 n \ge 32），因为记忆化是伪多项式的，记忆化只是保证一个状态只解决一次，但是不能减少需要解决的状态数，当 n 较大时，由于状态数以指数级增长，是无法在限定时间内解决的。

by j_steady @ 2022-08-06 11:41:20

@metaphysis 我写的记忆化wa了七个点，大佬有没有空看一下我的代码 qwq （讨论第一篇

by metaphysis @ 2022-08-06 14:48:52

@j_steady

好的，我看一下再给您回复。

by ssjl @ 2022-08-10 19:52:43

@metaphysis 我用dfs开O2能过，但是不开90pts

by ssjl @ 2022-08-10 19:53:54

@metaphysis 这个还能再优化一下么，tle了最后一个

#include <iostream>
#include <cstring>

using namespace std;

const int N = 3201;

int n, m;
int f[65][N];
int v[N], w[N], root;
int h[N], ne[N], e[N], idx;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u)
{
    for(int i = v[u]; i <= m; i ++)
        f[u][i] = v[u] * w[u];
    for(int i = h[u]; ~i; i = ne[i])
    {
        int son = e[i];
        dfs(son);
        for(int j = m; j >= v[u]; j --)
            for(int k = 0; k <= j - v[u]; k ++)
                f[u][j] = max(f[u][j], f[u][j-k] + f[son][k]);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    memset(h, -1, sizeof h);
    cin >> m >> n;
    m /= 10;
    root = n + 1;
    v[root] = 0, w[root] = 0;
    for(int i = 1; i <= n; i ++)
    {
        int p;
        cin >> v[i] >> w[i] >> p;
        v[i] /= 10;
        if(p == 0) add(root, i);
        else add(p, i);
    }
    dfs(root);
    cout << f[root][m] * 10 << '\n';
    return 0;
}

by metaphysis @ 2022-08-11 10:15:46

@ssjl

看是否可以记忆化。

by ___A__ @ 2023-04-29 22:13:10

@metaphysis 但一共就m个状态 和n没有关系