#P1400. sequence

    ID: 412 传统题 1000ms 512MiB 尝试: 16 已通过: 5 难度: 7 上传者: 标签>CF2300提高+/省选-完全背包折半枚举两半结果排序匹配双指针合并有序序列相向双指针消除被支配候选

sequence

题目描述

求满足下列条件的非负整数数列,满足: ∑i∈[1,N]Ai=X,∑i∈[1,N]AiP=Y∑_{i\in[1,N]}A_i=X,∑_{i\in[1,N]}A_i^P=Y 使得 ∑i∈[1,N]AiQ∑_{i\in[1,N]}A_i^Q的值最小。 输入: 第一行有五个整数,分别为n,p,q,x,yn,p,q,x,y。 其中 1≤n≤20,1≤p,q≤10,1≤x≤100,y1\leq n\leq 20,1\leq p,q\leq 10,1\leq x\leq 100,y 不超过COMP类型。

输入格式

第一行有五个整数,分别为 n,p,q,x,yn,p,q,x,y。 其中 1≤n≤20,1≤p,q≤10,1≤x≤100,y1\leq n\leq20,1\leq p,q\leq10,1\leq x\leq 100,y 不超过COMP类型。

输出格式

输出文件仅有一行,即 ∑AiQ∑A_i^Q 的最小值(不会超过COMP)。

4 2 3 20 130
920

本站数据版本约定

保证存在满足两项等式的非负整数数列,且最小目标值不超过 263−12^{63}-1。