MD
凹函数
题解
题意是多组数据，给定\(n,m\)，求定义域和值域分别为\([0,n],[0,m]\)的单调凹函数至多经过几个整点
考虑相邻两个经过整点的差，原问题等价于选出k个二维向量 \((x_i,y_i)\) ，满足 \(\sum\limits_k(x_i,y_i)=(n,m)\) ，且 \(\frac{y_i}{x_i}\) 两两不同， \(x_i,y_i\in N^*\) ，最大化\(k+1\)的值
方便起见，同时不改变答案，可以再等价变换为选出\(k\)个二维向量 \((x_i,y_i)\) ，满足 \(\sum x_i\leq n,\sum y_i \leq m\) ， \(gcd(x_i,y_i)=1\) ， \(x_i,y_i\in N^*\) ，最大化k+1$的值
为了回答多组询问，可以取\(N=3000\)，对 \(1\leq a,b\leq N\) 算出\(f(a,b)\)表示\(n=a,m=b\)时的答案
朴素做法是枚举\(N\)以内满足互质条件的二维向量，更新答案，时间复杂度为 \(O(N^4)\)
可以观察到\(f(N,N)\)在 \(O(N^{2/3})\) 数量级，于是可以把状态表示改为\(g(a,c)\)：\(x\)之和为\(a\)，选出\(c\)个向量，\(y\)之和的最小值，每选一个向量更新的时间复杂度从 \(O(N^2)\) 变为 \(O(N^\frac 53)\) ，时间复杂度降至 \(O(N^\frac {11} 3)\)
在选择向量时可以加入一个贪心策略而不失最优性：选一个向量，必须先选所有\(x,y\)同时小于等于它的其它向量。这些向量的和必须不超过\((N,N)\)。加入这一剪枝后，可选的向量变得非常少，在 \(O(N^\frac 23)\) 数量级，每个向量更新的时间复杂度仍为 \(O(N^\frac 53)\) ，因此总的时间复杂度降到 \(O(N^\frac 73)\) 。
这里用到两个观察得出的结论，以下给出证明：
- 答案在 \(O(N^{2/3})\) 数量级，这个可以由剪枝后向量的个数推出
- 剪枝后的向量个数在 \(O(N^\frac 23)\) 数量级
为方便证明，使用一个更弱的剪枝：选一个向量，必须先选所有\(x,y\)同时小于等于它的其它向量，这些向量的\(x+y\)之和不超过\(2N\)。
\(\sum\limits_N\sum\limits_N[gcd(X,Y)=1]\cdot \left [ \max\left ( \sum\limits_X \sum\limits_Y[gcd(x,y)=1]\cdot x , \sum\limits_X \sum\limits_Y[gcd(x,y)=1]\cdot y \right ) \leq N \right ]\)
$\leq \sum\limits_{1\leq X,Y\leq N} \left [ \max\left ( \sum\limits_{+\infty}\mu(d)d \sum\limits_{X/d} \sum\limits_{Y/d}x , \sum\limits_{+\infty}\mu(d)d \sum\limits_{X/d} \sum\limits_{Y/d}y \right ) \leq N \right ] $
\(\sum\limits_{1\leq X,Y\leq N}[XY\max(X,Y)\leq \Theta(N)]=O(n^\frac 23)\)
标准代码
C++ 11
#include<stdio.h>
#include<bits/stdc++.h>
const int inf=0x3f3f3f3f;
void maxs(int& a,int b){ if(a<b)a=b; }
void mins(int& a,int b){ if(a>b)a=b; }
int gcd(int x,int y){ return y?gcd(y,x%y):x; }
int n;
namespace sol{//n^4
int vf[307][307];
void cal(){
for(int x=1;x<=n;++x){
for(int y=1;y<=n;++y)if(gcd(x,y)==1){
for(int i=n;i>=x;--i)
for(int j=n;j>=y;--j)maxs(vf[i][j],vf[i-x][j-y]+1);
}
}
}
int get(int x,int y){
return vf[x][y];
}
}
namespace sol{//n^(8/3)logn
int s[4007];
int f[4007][4007];
void ins(int x,int y){
for(int i=n;i>=x;--i){
for(int j=n;j>=y;--j){
maxs(f[i][j],f[i-x][j-y]+1);
}
}
}
void cal(){
for(int i=1;i<=n;++i){
int s1=0;
for(int j=1;j<=n&&s[j]<=n*2;++j){
if(gcd(i,j)==1){
s1+=i+j;
if(s[j]+s1<=n*2)ins(i,j);
}
s[j]+=s1;
}
}
}
int get(int x,int y){
return f[x][y];
}
}
namespace sol{//n^(7/3)logn
int s[4007][2];
int fs[4007][407],sz[4007],o=0,err=0;
void ins(int x,int y){
for(int i=n;i>=x;--i){
bool st=0;
for(int j=0;j<=sz[i-x];++j){
int a=fs[i-x][j]+y;
if(a>n)break;
mins(fs[i][j+1],a);
}
if(fs[i][sz[i]+1]<inf)fs[i][++sz[i]+1]=inf;
}
}
int get(int x,int y){
return std::upper_bound(fs[x],fs[x]+sz[x]+1,y)-fs[x]-1;
}
void cal(){
for(int i=0;i<=n;++i)fs[i][1]=inf;
for(int i=1;i<=n;++i){
int s0=0,s1=0;
for(int j=1;j<=n&&std::max(s[j][0],s[j][1])<=n;++j){
if(gcd(i,j)==1){
s0+=i;
s1+=j;
if(std::max(s[j][0]+s0,s[j][1]+s1)<=n)ins(i,j);
}
s[j][0]+=s0;
s[j][1]+=s1;
}
}
}
}
int q,qs[10007][2];
int main(){
n=1;
assert(scanf("%d",&q)==1);
assert(1<=q&&q<=10000);
for(int i=0;i<q;++i){
assert(scanf("%d%d",qs[i],qs[i]+1)==2);
assert(qs[i][0]>=1&&qs[i][0]<=3000);
assert(qs[i][1]>=1&&qs[i][1]<=3000);
n=std::max(n,std::max(qs[i][0],qs[i][1]));
}
using namespace sol3;
cal();
for(int i=0;i<q;++i)printf("%d\n",get(qs[i][0],qs[i][1])+1);
return 0;
}