汽车网站cms,网站备案通管局,友情链接有哪些作用,网站seo优化徐州百度网络Portal.
对于每一个拨圈#xff0c;分别考虑它对答案的影响。但注意到当前拨圈的最优转动方案会对之后的拨圈转动方案产生影响#xff0c;即有后效性。
后效性的产生可以通过随机化改变考虑的顺序解决。
代码实现的一点细节#xff1a;先考虑出每个圈的最优转动方案…Portal.
对于每一个拨圈分别考虑它对答案的影响。但注意到当前拨圈的最优转动方案会对之后的拨圈转动方案产生影响即有后效性。
后效性的产生可以通过随机化改变考虑的顺序解决。
代码实现的一点细节先考虑出每个圈的最优转动方案更新在此方案下的当前局面每一行的最大值、最小值。把 n n n 个拨圈全部统计完之后更新当前考虑顺序下的答案。
注意到 random_shuffle 比 shuffle 更好地快速逼近答案。
#include bits/stdc.h
using namespace std;const int maxn5e45;
int a[maxn][5],mx[5],mi[5],T,k;void solve()
{int n;cinn;for(int j1;jk;j) for(int i1;in;i) cina[i][j];int tt300,ans0x3f3f3f;while(tt--){// mt19937 rd(time(0));// shuffle(a1,an1,rd);random_shuffle(a1,an1);memset(mx,-0x3f3f3f,sizeof mx),memset(mi,0x3f3f3f,sizeof mi);for(int i1;in;i){int minstp0,minv0x3f3f3f;for(int stp0;stpk;stp){int vv0;for(int j1;jk;j){int pos(jstp-1)%k1;vvmax(vv,max(mx[j],a[i][pos])-min(mi[j],a[i][pos]));}if(vvminv) minstpstp,minvvv;}for(int j1;jk;j) {int nowpos(jminstp-1)%k1;mx[j]max(mx[j],a[i][nowpos]),mi[j]min(mi[j],a[i][nowpos]);}if(minvans) break;//到当前局面松散度已经超过原答案// coutminstp minvendl;}int tmp0;for(int i1;ik;i) tmpmax(tmp,mx[i]-mi[i]);ansmin(tmp,ans);}coutans\n;
}int main()
{cinTk;while(T--) solve();return 0;
}
