# 【P1270 “访问”美术馆】题解([P1270 “visit” Art Museum] explanation)-其他

## 【P1270 “访问”美术馆】题解([P1270 “visit” Art Museum] explanation)

### code

// Problem: P1270 “访问”美术馆
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1270
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define M 600
//#define mo
#define N 510
struct node
{
int x, y, z, n;
}d[N*4];
int n, m, i, j, k;
int a[N], dp[N][M], h[N], f[M];
int zhan[N], top, x, y, s;

void cun(int x, int y, int z)
{
// printf("%lld %lld %lld\n", x, y, z);
++m;
d[m].x=x; d[m].y=y; d[m].z=z;
d[m].n=h[x]; h[x]=m;
}

void dfs(int x)
{
if(a[x])
{
for(int i=0; i<=a[x]&&i*5<=s; ++i)
dp[x][i*5]=i;
for(int i=1; i<=s; ++i)
if(!dp[x][i]) dp[x][i]=dp[x][i-1];
// printf("dp[%lld]=%lld\n", x, dp[x][s]);
return ;
}
for(int g=h[x]; g; g=d[g].n)
{
int y=d[g].y;
dfs(y);
// memset(f, 0, sizeof(f));
for(int j=0; j<=s; ++j) f[j]=dp[x][j];
for(int j=s; j>=0; --j)
for(int i=j; i>=d[g].z*2; --i)
dp[x][j]=max(dp[x][j], dp[y][i-d[g].z*2]+f[j-i]);
}
// printf("dp[%lld]=%lld\n", x, dp[x][s]);
}

signed main()
{
//	freopen("tiaoshi.in", "r", stdin);
//	freopen("tiaoshi.out", "w", stdout);
zhan[top=1]=k=1;
while(scanf("%lld%lld", &x, &y)!=EOF)
{
if(y==0) cun(zhan[top--], ++k, x), zhan[++top]=k, zhan[++top]=k;
else cun(zhan[top--], ++k, x), a[k]=y;
}
dfs(1);
printf("%lld", dp[1][s]);
return 0;
}

————————

Typical tree DP.

Let \ (DP (x, I) \) represent the maximum value of works that stay in the subtree of \ (x \) for \ (I \) seconds.

There are some order and details in the actual implementation, which can be adjusted.

The edge building aspect can be implemented with a stack.

### code

// Problem: P1270 “访问”美术馆
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1270
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define M 600
//#define mo
#define N 510
struct node
{
int x, y, z, n;
}d[N*4];
int n, m, i, j, k;
int a[N], dp[N][M], h[N], f[M];
int zhan[N], top, x, y, s;

void cun(int x, int y, int z)
{
// printf("%lld %lld %lld\n", x, y, z);
++m;
d[m].x=x; d[m].y=y; d[m].z=z;
d[m].n=h[x]; h[x]=m;
}

void dfs(int x)
{
if(a[x])
{
for(int i=0; i<=a[x]&&i*5<=s; ++i)
dp[x][i*5]=i;
for(int i=1; i<=s; ++i)
if(!dp[x][i]) dp[x][i]=dp[x][i-1];
// printf("dp[%lld]=%lld\n", x, dp[x][s]);
return ;
}
for(int g=h[x]; g; g=d[g].n)
{
int y=d[g].y;
dfs(y);
// memset(f, 0, sizeof(f));
for(int j=0; j<=s; ++j) f[j]=dp[x][j];
for(int j=s; j>=0; --j)
for(int i=j; i>=d[g].z*2; --i)
dp[x][j]=max(dp[x][j], dp[y][i-d[g].z*2]+f[j-i]);
}
// printf("dp[%lld]=%lld\n", x, dp[x][s]);
}

signed main()
{
//	freopen("tiaoshi.in", "r", stdin);
//	freopen("tiaoshi.out", "w", stdout);