公司网站建设模块简介,aso关键字优化,wordpress关键词采集文章,建筑人才网 中级职称评审费用CF1354F. Summoning Minions
Solution VPVPVP结束十分钟后AC,qwqAC,qwqAC,qwq。
首先因为ai,bi≥0a_i,b_i \geq 0ai,bi≥0#xff0c;所以所有东西全用一次答案不会变劣#xff0c;留到最后的集合大小一定为kkk。
如果我们知道留到最后的集合Sx1,x2...xkS{x_1,x_2...x…CF1354F. Summoning Minions
Solution
VPVPVP结束十分钟后AC,qwqAC,qwqAC,qwq。
首先因为ai,bi≥0a_i,b_i \geq 0ai,bi≥0所以所有东西全用一次答案不会变劣留到最后的集合大小一定为kkk。
如果我们知道留到最后的集合Sx1,x2...xkS{x_1,x_2...x_{k}}Sx1,x2...xk考虑让U−SU-SU−S中的点贡献最大我们的方案显然是先加入x1,x2...xk−1{x_1,x_2...x_{k-1}}x1,x2...xk−1然后把y∈U−Sy \in U-Sy∈U−S都插入删除一遍再放入一个xkx_kxk因此总贡献为 (∑i1k−1axibxi∗(i−1))(∑i1n−kbyi∗(k−1))(k−1)bxkaxk(\sum_{i1}^{k-1}a_{x_i}b_{x_i}*(i-1))(\sum_{i1}^{n-k}b_{y_i}*(k-1))(k-1)b_{x_k}a_{x_k} (i1∑k−1axibxi∗(i−1))(i1∑n−kbyi∗(k−1))(k−1)bxkaxk 即 (∑i1kaxibxi∗(i−1))(∑i1n−kbyi∗(k−1))(\sum_{i1}^{k}a_{x_i}b_{x_i}*(i-1))(\sum_{i1}^{n-k}b_{y_i}*(k-1)) (i1∑kaxibxi∗(i−1))(i1∑n−kbyi∗(k−1)) 于是我们发现一个性质在SSS确定时aia_iai的顺序不影响答案bib_ibi从小到大答案最优。
因此我们将所有数按bib_ibi排序再通过选择SSS来使答案最优我们考虑DP令fi,jf_{i,j}fi,j表示前iii个数中已经选择了x1...xj{x_1...x_j}x1...xj的最大值。 转移时考虑枚举第iii个人加入SSS或不加入SSS的贡献 fi,jmin(fi−1,j−1aibi∗(j−1),fi−1,jbi∗(k−1))f_{i,j}min(f_{i-1,j-1}a_ib_i*(j-1),f_{i-1,j}b_i*(k-1))fi,jmin(fi−1,j−1aibi∗(j−1),fi−1,jbi∗(k−1)) 顺便记录方案即可。
时间复杂度O(nkT)O(nkT)O(nkT)
Code
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods1e97;
const int MAXN5005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
int a[105],b[105],f[105][105],flag[105],frm[105][105],id[105];
vectorint V;
signed main()
{int Caseread();while (Case--){memset(f,-INF,sizeof f);memset(frm,0,sizeof frm);memset(flag,0,sizeof flag);int nread(),kread();for (int i1;in;i) a[i]read(),b[i]read(),id[i]i;sort(id1,idn1,[](int x,int y){ return b[x]b[y]; });V.clear();f[0][0]0;for (int i1;in;i)for (int j0;jk;j) {if (jupmax(f[i][j],f[i-1][j-1]a[id[i]]b[id[i]]*(j-1))) frm[i][j]1;if (upmax(f[i][j],f[i-1][j]b[id[i]]*(k-1))) frm[i][j]2;}int nwk;for (int in;i1;i--)if (frm[i][nw]1) V.PB(id[i]),nw--;else flag[id[i]]1;reverse(V.begin(),V.end());printf(%d\n,n*2-k);for (int i0;ik-1;i) printf(%d ,V[i]);for (int i1;in;i)if (flag[i]) printf(%d -%d ,i,i);printf(%d\n,V[k-1]);}return 0;
}
