企业网站建立流程的第一步是什么,企业网站开发周期,WordPress七牛防盗链,中国室内设计网站有哪些智商不够啊#xff0c;咋想到贪心的#x1f605;
非常经典的贪心模型#x1f914;
首先#xff0c;从小到大将每个 i i i插入到排列中#xff0c;用 D P DP DP记录还有多少个位置可以插入#xff0c;可以通过钦定新插入的位置左右两边是否继续插入数来提前计算贡献。注…智商不够啊咋想到贪心的
非常经典的贪心模型
首先从小到大将每个 i i i插入到排列中用 D P DP DP记录还有多少个位置可以插入可以通过钦定新插入的位置左右两边是否继续插入数来提前计算贡献。注意分 i i i和 s , t s,t s,t的大小关系讨论。这个做法的时间复杂度是 O ( n 2 ) O(n^2) O(n2)并且转移的情况比较多估计要调半天。
但是注意到我们可以 直接贪心 。发现本质上就是每次加入两个固定的数然后将原来的一个数替换掉并且一个数只能被替换一次。因此每次贪心的选最优的位置插入即可。
代码可以在 5 min 5\min 5min内完成。
另一道直接贪心的题CF573E Bear and Bowling
#includebits/stdc.h
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N5005;
int n,s,t,to[N];
ll a[N],b[N],c[N],d[N],X[N],res;
ll calc(int i,int j){if(ij)return X[i]-X[j]c[i]b[j];return X[j]-X[i]d[i]a[j];
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnst;for(int i1;in;i)cinX[i];for(int i1;in;i)cina[i];for(int i1;in;i)cinb[i];for(int i1;in;i)cinc[i];for(int i1;in;i)cind[i];to[s]t;for(int i1;in;i){if(is||it)continue;pairll,inttmp{inf,0};for(int js;j!t;jto[j]){tmpmin(tmp,{calc(j,i)calc(i,to[j])-calc(j,to[j]),j});}to[i]to[tmp.se],to[tmp.se]i;}for(int is;i!t;ito[i])rescalc(i,to[i]);coutres;
}
