山东枣庄滕州网站建设,做指甲的网站叫什么名字来着,凡客装修,怎么做系统网站题意
本题给我们给我们两种货币初始金额 每种货币分别对应能买不同种类的喷泉 每个喷泉有花费和价值 问我们如果单纯建造两个喷泉在限定金额内的最大值
分析
考虑一下 发现有三种情况 #xff11; 两个喷泉从coin中里建造 #xff12; 两个喷泉从diamond中建造 两个喷泉从coin中里建造 两个喷泉从diamond中建造 一边一个 输出 表示找不出两个合法的可行解 第种情况还好判断 就是在两边一遍选一个金额限度中价值最大的就可以了 关键是第种 我们考虑专门建造两种相同种类的喷泉的情况 也就是在限定金额中选出两个价值和最大的情况 这个就相当于我们选择了一个喷泉 然后再在coin-cost的金额范围内再选一个最大的 那么也就是说对于每一个喷泉 我们在一定区间内选一个价值最大的 这个区间可以设置为 -(coin-cost)范围 这样当我们枚举每一个喷泉时 在选一个前面的最大的喷泉 就可以把所有的可能遍历到 那么这里就可以用二分搜索结构处理区间最大值 区间的下标的意义在当前花费下标 #includecstdio
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int maxn 100010;
int tc[maxn],td[maxn],n,c,d;
void add(int tre[],int x,int val){while(xmaxn){tre[x] max(tre[x],val);xx(-x);}
}
int query(int tre[],int x){int res0;while(x){res max(res,tre[x]);x-x(-x);}return res;
}
int main()
{int ans0,Ma0;scanf(%d%d%d,n,c,d);for(int i1;in;i){int co,val;char o[5];scanf(%d%d%s,val,co,o);if(o[0]C){Ma query(td,d);// 如果在里面查不到数 就返回 Ma 0if(coc)continue;// 后面的都不必处理如果当前喷泉话费已经超过限制 那么就不必插入树中也不必选一个c-cost中的最大Ma max(Ma,query(tc,c-co));// 由于当前物品 无论怎样都要拿 我们不如从两个同类中和另外一类中拿那个最大的 如果相应金额下没有物品 也返回 所以两种情况都查不到有效值 返回add(tc,co,val);//边查询边更新 防止查询到自己}else{Ma query(tc,c);if(cod)continue;Ma max(Ma,query(td,d-co));add(td,co,val);}if(Ma)ans max(ans,Maval);//每次更新结果 如果能查到结果才更新 如果查不到 就说明不足两个物品 就不更新}printf(%d\n,ans);return 0;
}
/*
这种写法的神奇之处就在于可以把所有情况遍历到
对于每一个新物品 我们考虑在同类中找一个可以买得起的组合 和 另一类中买的起的组合中选一个最大的
前者会把所有同类中的可行解都遍历到 后者会考虑到一边一个的情况
最优解如果是同类中选两个 那么一定是先选一个物品 然后在剩余金额中在选一个买的起的最大价值的
那么这里就是枚举选的第一个物品 直接在数据处理的时候就可以做到
然后选完之后再把当前物品插入到树状数组中 所以不会重复选择当前物品
如果一边不足两个 那么一定会查到 与另外一边的种类组合 如果另外一边的买不起 那么就会查到
所以输出的情况中 买不起就不会插入 那么就搜不到这个数据 所以查找只会查询买得起的
所以两个同类的 两个不同类的 以及不足两个的 买不起的情况都可以考虑到
*/
