Tmbcan @ 2024-07-30 15:55:27

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T&x){
    int w=0;x=0;
    char ch = getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9'){
        x = (x<<1)+(x<<3)+(ch^48);
        ch = getchar();
    }
    if(w) x=-x;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
    read(t);read(args...);
}
const int N = 4e4;
int V,n;
int ans[70][N];
int to[N],nex[N],w[N],v[N];
int head[N],edge_num;
inline void add(int a,int b,int ww,int vv){

}
int vis[N];
inline void dfs(int now){
//  cout << now << endl;
    vis[now] = 1;
    for(int i=head[now];i!=-1;i=nex[i]){
        int tto = to[i];
        if(vis[tto]) continue;
        vis[tto] = 1;
        dfs(tto);
        for(int j=V-w[now];j>=0;--j){
            for(int k=0;k<=j;++k){
                if(ans[now][j]<ans[now][j-k]+ans[tto][k]) ans[now][j]=ans[now][j-k]+ans[tto][k];
            }
        }
    }
    for(int i=V;i>=0;--i){
        if(i<w[now]) ans[now][i] = 0;
        else ans[now][i] = ans[now][i-w[now]]+v[now];
    }
}
int main(){
    read(V,n);
    memset(head,-1,sizeof(head));
    for(int i=1,vv,q;i<=n;++i){
        read(w[i],vv,q);
        to[++edge_num] = i;
        nex[edge_num] = head[q];
        head[q] = edge_num;
        v[i] = vv*w[i]/10;
    }
    dfs(0);
    printf("%d",ans[0][V]*10);
    return 0;
}

by _Kenma_ @ 2024-07-30 18:16:37

@Tmbcan 复杂度假了，O（n m^{2}） 应该过不了吧

上下界优化不是万能的

by _Kenma_ @ 2024-07-30 18:19:32

要不你试试 /100 ?

by _Kenma_ @ 2024-07-30 18:22:32

破案了,你把价值除以10没意义，应该把体积除以10

AC code

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T&x){
    int w=0;x=0;
    char ch = getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9'){
        x = (x<<1)+(x<<3)+(ch^48);
        ch = getchar();
    }
    if(w) x=-x;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
    read(t);read(args...);
}
const int N = 2e5+5;
int V,n;
int ans[70][N];
int to[N],nex[N],w[N],v[N];
int head[N],edge_num;
inline void add(int a,int b,int ww,int vv){

}
int vis[N];
inline void dfs(int now){
//  cout << now << endl;
    vis[now] = 1;
    for(int i=head[now];i!=-1;i=nex[i]){
        int tto = to[i];
        if(vis[tto]) continue;
        vis[tto] = 1;
        dfs(tto);
        for(int j=V-w[now];j>=0;--j){
            for(int k=0;k<=j;++k){
                if(ans[now][j]<ans[now][j-k]+ans[tto][k]) ans[now][j]=ans[now][j-k]+ans[tto][k];
            }
        }
    }
    for(int i=V;i>=0;--i){
        if(i<w[now]) ans[now][i] = 0;
        else ans[now][i] = ans[now][i-w[now]]+v[now];
    }
}
int main(){
    read(V,n);
    V/=10;
    memset(head,-1,sizeof(head));
    for(int i=1,vv,q;i<=n;++i){
        read(w[i],vv,q);
        to[++edge_num] = i;
        nex[edge_num] = head[q];
        head[q] = edge_num;
        w[i]/=10;
        v[i] = vv*w[i];
    }
    dfs(0);
    printf("%d",ans[0][V]*10);
    return 0;
}

by _Kenma_ @ 2024-07-30 18:23:26

@Tmbcan

还有怎么删不了之前的唐氏回答啊

by hsy8116 @ 2024-07-31 08:22:23

@Kenma 大佬太厉害了，我们俩调了一下午。

by _Kenma_ @ 2024-07-31 08:28:25

啊？你们在zzz那里上课呢吗

@Hsy122313814

by Tmbcan @ 2024-07-31 08:28:52

@Kenma

xtz大佬%%%%%%%

by _Kenma_ @ 2024-07-31 08:29:37

啊？

by Tmbcan @ 2024-07-31 08:30:32

@Kenma 我们两个蒟蒻在听普及组

根本听不懂一点

by _Kenma_ @ 2024-07-31 08:31:47

假