题目大意
猜数,每次询问一个数x返回大于小于等于,代价是数的大小x
设C(n)表示数在[1,n]的最优策略下的答案,求\(\sum_{i=1}^{200000}C(i)\)
题解
显然可以n^3dp:设f[i,j]表示当前数的范围在[i,j]的答案,然后oeis即可得到n^2做法
考虑如何n^2,转移枚举k然后min(max(f[i,k-1]+k,f[k+1,j]+k))->f[i,j],这样是n^3
枚举j,然后从j往前枚举i,把max拆开发现前一段是f[k+1,j],后一段是f[i,k+1],因为小区间一定比包含它的区间更优
所以单调维护分界点k0,把前面的丢到单调队列,后面的直接算k0,因为如果继续增大则f和k都会增大,显然不优
这样就可以n^2了,但是空间开不下
把n^3dp的决策点打表出来可以发现决策点到右端点的距离大约在n/logn左右,所以每次断开后的右段长度不长,而答案是Σ[1,i],所以断开后只会产生[1,i]和[j-s+1~j,j]
设s=n/logn,维护一个s^2的滚动数组,每次求出[i-s+1,i]的dp值,然后即可求[1,i]的值
时间复杂度\(O(n^2/\log n)\),空间复杂度\(O(n^2/\log^2n)\),60s跑完
然后就看到了thread里3s跑完1e7的神仙老鸽
code
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ll long long
#define N 13000
#define file
using namespace std;
ll g[N+1][N+1],ans,inf;
ll f[200001],s1,s2,s;
int n,i,j,k,l,S,ed,h,t;
int d[200001];
int I[200001];
ll get(int x,int y)
{
if (x>=y) return 0;
return g[I[y]][y-x];
}
int main()
{
freopen("PE328.in","r",stdin);
#ifdef file
freopen("PE328.out","w",stdout);
#endif
memset(g,1,sizeof(g)),inf=g[0][0];
scanf("%d",&n);S=min(n,N);
fo(i,1,n) I[i]=i%N+1;
fo(i,2,n)
{
f[i]=inf,memset(g[I[i]],1,sizeof(g[I[i]]));
g[I[i]][0]=0;
ed=max(i-S+1,1);k=i;h=1,t=0;
fd(j,i-1,ed)
{
while (k>j && get(j,k-2)>get(k,i)) --k;
while (h<=t && k<=d[h]) ++h;
while (h<=t && get(d[t]+1,i)+d[t]>=get(j+1,i)+j) --t;
d[++t]=j;
s1=get(d[h]+1,i)+d[h];
s2=get(j,k-1)+k;
g[I[i]][i-j]=min(s1,s2);
}
fo(j,ed,i) s=get(j+1,i),s=max(s,f[j-1])+j,f[i]=min(f[i],s);
}
fo(i,1,n) ans+=f[i];
printf("%lld\n",ans);
fclose(stdin);
fclose(stdout);
return 0;
}