建筑公司网站源码/北京优化网站公司

题目链接

题目链接

题意

魔法值和财富值初始为0，帕秋莉将捡到的n块石头排成一排，并决定将一些石头点为黄金，对于第i块石头，如果将其变为黄金，会增加ai的财富，消耗bi的魔法（就算魔法值不够，也可以操作，操作后魔法值归零）
否则，帕秋莉将会回复ci的魔法，但减少di的财富（财富值同理，可以无限制减少）
如何决策，可以使自己最后的收益值最大只需要输出最大收益=财富值*魔法值

（提示：数值不会变为负数，即任何时候，如果数值小于了0，它会立即变为0）

思路

• 数据范围<=15, dfs求解

参考代码

#include<bits/stdc++.h>
using namespace std;
struct node
{int a,b,c,d;
};
node aa[20];
long long ans=0;
int n;
void dfs(long long wealth, long long  magic,long long  depth)
{if(depth==n){ans=max(ans,wealth*magic);return ;}int t=0;if(magic>=aa[depth].b) t=magic-aa[depth].b;else t=0;dfs(wealth+aa[depth].a,t,depth+1);\int t1=0;if(wealth>=aa[depth].d) t1=wealth-aa[depth].d;else t1=0;dfs(t1,magic+aa[depth].c,depth+1);}
int main()
{cin>>n;for(int i=0;i<n;i++){cin>>aa[i].a>>aa[i].b>>aa[i].c>>aa[i].d;}dfs(0,0,0);cout<<ans<<endl;
}