访问美术馆的加强版
思路：
和上一题相比，该题只是给展室中的画定义了价值和耗费时间，对于每个展室中的话跑01背包。
dp[i][j]表示到第i条走廊时，花费j时间能够得到的画的最大价值。
在读入数据的时候进行dp即可。
代码：
///#pragma GCC optimize(3) ///#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") ///#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll inline ll read() { ll 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*10+ch-'0'; ch=getchar(); } return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } ll ksm(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } const int inf=0x3f3f3f3f,mod=1000000007; const ll INF = 0x3f3f3f3f3f3f3f3f; const int maxn=1e6+7,maxm=3e5+7,N=1e6+7; const double PI = atan(1.0)*4; struct node { int time,cnt; } a[maxn]; int dp[2100][2100]; int w[maxn],c[maxn],s; void dfs(int u) { a[u].time=read(); a[u].cnt=read(); a[u].time=a[u].time*2; if(a[u].cnt>0) ///是展室 { for(int i=1; i<=a[u].cnt; i++) { w[i]=read(); c[i]=read();///读入数据 } for(int i=1; i<=a[u].cnt; i++) for(int j=s; j>=a[u].time+c[i]; j--)///要注意走廊花费的时间 dp[u][j]=max(dp[u][j],dp[u][j-c[i]]+w[i]);///01背包问题 } else ///不是展室 枚举分给左子树的时间 { dfs(u<<1); dfs(u<<1|1);///先读入子树的数据 for(int i=a[u].time; i<=s; i++) ///枚举子树的总的时间 { for(int k=0; k<=i-a[u].time; k++) ///枚举给左子树的时间 { dp[u][i]=max(dp[u][i],dp[u<<1][k]+dp[u<<1|1][i-k-a[u].time]); } } } } int main() { s=read(); s--; dfs(1); out(dp[1][s]); return 0; }
