P1270 输入好题

#include<cstdio>
#define maxn 1001
using namespace std;
inline int max(int a,int b){return a > b ? a : b;}
inline int min(int a,int b){return a < b ? a : b;}
int tot,dp[maxn][maxn];
struct node{int cost,val;}tree[maxn<<2];
void init(int x){
	scanf("%d%d",&tree[x].cost,&tree[x].val);
	tree[x].cost <<=1;
	if(!tree[x].val){init(x<<1); init(x <<1|1);}
}
int dfs(int x,int tot){
	if(dp[x][tot] > 0 || !tot) return dp[x][tot];
	if(tree[x].val) return dp[x][tot] = min(tree[x].val,(tot-tree[x].cost)/5);
	for(int k = 0;k <= tot - tree[x].cost;k++)
	dp[x][tot] = max(dp[x][tot],dfs(x<<1,k)+dfs(x<<1|1,tot-tree[x].cost-k));
	return dp[x][tot];
}
int main(){
	scanf("%d",&tot);tot--;
    init(1);
    printf("%d",dfs(1,tot));
    return 0;
}

P1270 输入好题

原文：https://www.cnblogs.com/shikeyu/p/13440564.html