红木家具网站建设总体规划,wordpress 修改固定链接,百度指数代表什么意思,小说网站建站程序正题
题目链接:https://www.luogu.com.cn/problem/P6563 题目大意
长度为nnn的序列aia_iai#xff0c;现在有一个随机[1,n][1,n][1,n]的整数#xff0c;每次你可以花费aia_iai询问这个数字是否大于iii#xff0c;求猜出所有数至少要多少花费。 T≤500,∑n≤7000T\leq …正题
题目链接:https://www.luogu.com.cn/problem/P6563 题目大意
长度为nnn的序列aia_iai现在有一个随机[1,n][1,n][1,n]的整数每次你可以花费aia_iai询问这个数字是否大于iii求猜出所有数至少要多少花费。
T≤500,∑n≤7000T\leq 500,\sum n\leq 7000T≤500,∑n≤7000
保证aia_iai单调不降 解题思路
考虑区间dpdpdp设fl,rf_{l,r}fl,r表示猜出区间[l,r][l,r][l,r]的最小花费。
最基本的转移就是 fl,rmin{max{fl,k,fk1,r}ak}(k∈[l,r))f_{l,r}min\{\ max\{f_{l,k},f_{k1,r}\}a_k\ \}(\ k\in[l,r)\ )fl,rmin{ max{fl,k,fk1,r}ak }( k∈[l,r) )
然后考虑如何优化转移。
因为里面有个maxmaxmax我们可以对于一个l,rl,rl,r考虑找到一个最小的zzz满足fl,zfz1,rf_{l,z}f_{z1,r}fl,zfz1,r那么zzz以后的都是用fl,zf_{l,z}fl,z以前的都是用fz1,rf_{z1,r}fz1,r。
这个在右端点固定左端点向左时zzz是不升的所以不用二分带logloglog。
对于取fl,kakf_{l,k}a_kfl,kak的那一部分aka_kak和fl,zf_{l,z}fl,z都随着kkk增大不降所以直接取fl,zazf_{l,z}a_zfl,zaz。
对于fk1,rakf_{k1,r}a_kfk1,rak的那一部分kkk的限制会不断缩小所以用一个单调队列维护就可以了。
时间复杂度O(∑n2)O(\sum n^2)O(∑n2) code
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N7200;
int T,n,a[N];
long long f[N][N];
dequeint q;
long long calc(int k,int r){if(k1)return 1e18;return f[r][k1]a[k];
}
signed main()
{scanf(%d,T);while(T--){scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]);for(int i1;in;i)for(int j1;jn;j)if(i!j)f[i][j]1e18; for(int r2;rn;r){q.clear();q.push_back(r-1);for(int lr-1,zr-1;l1;l--){while(zlf[z-1][l]f[r][z])z--;while(!q.empty()q.front()z)q.pop_front();if(!q.empty())f[r][l]calc(q.front(),r);f[r][l]min(f[r][l],f[z][l]a[z]);if(l1)continue;while(!q.empty()calc(q.back(),r)calc(l-1,r))q.pop_back();q.push_back(l-1);}}printf(%lld\n,f[n][1]);}
}
