关于决策单调性
四边形不等式与决策单调性
有如下的定理：
如果对于 \(a
对于方程：
\[dp[??][??]=min?(dp[??][??]+dp[??+1][??]) \]定义使 \(dp[??][??]\) 取到最优值的 \(??\) 称为 \(dp[??][??]\) 决策点，记作 \(??[??][??]\)。
若 \(dp[??][??]\) 满足四边形不等式则 \(??[??][???1]≤s[??][??]≤??[??+1][??]\) 。
这样的话，在求 \(s[i][j]\) 时只需从 \(s[i][j-1]\) 循环到 \(s[i+1][j]\)
枚举长度 \(L\)，总时间为：
\(∑_{??=1}^{?????+1}\limits (??[??+1][??+???1]???[??][??+???2]) =??[?????+2][??]???[1][???1]=??(??)\)
故总时间复杂度为 \(O(??^2)\)
[IOI2013]wombats
对于决策单调性，可以用四边形不等式证明，实际中更常用的方法是感性理解以及打表找规律
本题中，可以发现最优路径不会交叉，因此利用上面的方式将 \(Floyd\) 从 \(O(n^3)\) 优化到 \(O(n^2)\)
点击查看代码
#include
using namespace std;
int R,C,E;
int h[5005][205],v[5005][205],Loc[205][205];
struct mat{
int a[205][205];
inline void init(int _x=1e9){
for(int i=0;i<=R+1;i++){
for(int j=0;j<=R+1;j++)a[i][j]=1e9;
a[i][i]=_x;
}
}
inline int* operator [](int t){
return a[t];
}
inline mat operator *(mat b){
mat res;res.init();
for(int i=0;i<=R+1;i++){
for(int j=0;j<=R+1;j++)Loc[i][j]=0;
}
for(int i=1;i<=R;i++){
for(int j=R;j>=1;j--){
int l=(1,Loc[i-1][j]?Loc[i-1][j]:1),r=(Loc[i][j+1]?Loc[i][j+1]:R);
for(int t=l;t<=r;t++){
if(res[i][j]>a[i][t]+b[t][j]){
res[i][j]=a[i][t]+b[t][j];
Loc[i][j]=t;
}
}
}
}return res;
}
}tree[805];
inline void calc(int l,int r,mat &mp){
mp.init(0);
for(int i=l;i<=r;i++){
for(int j=1;j<=R;j++){
for(int t=1;t<=R;t++)mp[j][t]+=v[i][t];
}
for(int j=1;j<=R;j++){
for(int t=1;t<=R;t++)mp[j][t]=min(mp[j][t],mp[j][t-1]+h[i][t-1]);
for(int t=R;t>=1;t--)mp[j][t]=min(mp[j][t],mp[j][t+1]+h[i][t]);
}
}
}
void build(int l=1,int r=C,int i=1){
if(r-l<25){
calc(l,r,tree[i]);return ;
}
int mid=(l+r)>>1;
build(l,mid,i<<1);build(mid+1,r,i<<1|1);
tree[i]=tree[i<<1]*tree[i<<1|1];
}
void update(int loc,int l=1,int r=C,int i=1){
if(locr)return ;
if(r-l<25){
calc(l,r,tree[i]);return ;
}
int mid=(l+r)>>1;
update(loc,l,mid,i<<1);update(loc,mid+1,r,i<<1|1);
tree[i]=tree[i<<1]*tree[i<<1|1];
}
int main(){
scanf("%d%d",&C,&R);
for(int i=1;i<=C;i++){
for(int j=1;j [IOI2000]邮局
点击查看代码
#include
using namespace std;
int v,p;
int dp[3005][305],w[3005][3005];
int a[3005],loc[3005][305];
inline void init(){
for(int i=1;i<=v;i++){
for(int j=i;j<=v;j++)w[i][j]=w[i][j-1]+a[j]-a[(i+j)>>1];
}
}
int main(){
scanf("%d%d",&v,&p);
for(int i=1;i<=v;i++)scanf("%d",&a[i]);
sort(a+1,a+v+1);init();
memset(dp,0x3f,sizeof(dp));dp[0][0]=0;
for(int i=1;i<=v;i++){
for(int j=p;j;j--){
int l=(loc[i-1][j]?loc[i-1][j]:1),r=(loc[i][j+1]?loc[i][j+1]:i);
for(int t=l;t<=r;t++){
if(dp[i][j]>dp[t-1][j-1]+w[t][i]){
dp[i][j]=dp[t-1][j-1]+w[t][i];
loc[i][j]=t;
}
}
}
}printf("%d",dp[v][p]);
return 0;
}
分治优化 \(dp\)
设 \(calc(l,r,L,R)\) 表示要求的区间为 \([l,r]\)，决策区间为 \([L,R]\)，每次选 \(l,r\) 中点 \(mid\) 暴力求解其决策点 \(p\)
然后递归 \(calc(l,mid-1,L,p)\) 和 \(calc(mid+1,r,p,R)\)。
递归 \(log\) 层，每层暴力求 \(p\) 的复杂度之和为 \(n\)，故总复杂度为\(??(?? log ???)\)
CF321E Ciel and Gondolas
点击查看代码
#include
using namespace std;
int n,k;
void Read( int &x ) {
x = 0; int f = 1;
char s = getchar( );
for( ; s < '0' || s > '9' ; s = getchar( ) ) f = s == '-' ? -f : f;
for( ; s >= '0' && s <= '9' ; s = getchar( ) ) x = x * 10 + s - '0';
x *= f;
}
int a[4005][4005];
long long sum[4005][4005],dp[805][4005];
void solve(int lim,int l=1,int r=n,int ql=0,int qr=n){
if(l>r)return ;
int mid=(l+r)>>1,loc=0;
for(int i=ql;i<=mid&&i<=qr;i++){
if(dp[lim][mid]>dp[lim-1][i]+sum[i+1][mid]){
dp[lim][mid]=dp[lim-1][i]+sum[i+1][mid];
loc=i;
}
}
solve(lim,l,mid-1,ql,loc);solve(lim,mid+1,r,loc,qr);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)Read(a[i][j]);
}
for(int i=1;i<=n;i++)sum[i][i]=a[i][i];
for(int len=1;len<=n;len++){
for(int i=1;i+len<=n;i++){
int j=i+len;
sum[i][j]=sum[i][j-1]+sum[i+1][j]+a[i][j]+a[j][i]-sum[i+1][j-1];
}
}
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=k;i++)solve(i);
printf("%lld",dp[k][n]/2);
return 0;
}
CF868F Yet Another Minimization Problem
点击查看代码
```cpp #includereturn 0;
点击查看代码
```cpp #include单调栈优化 \(dp\)
在单调栈中保存三元组 \((p,l,r)\) 表示 \([l,r]\) 这些位置的决策是 \(p\)，初始时保存 \((0,1,n)\)，每处理一个位置，这个位置就可以作为决策。
计算单调栈中哪些决策应修改为当前位置，这些位置一定是一个后缀，如果某一个三元组左端点还不如新的决策优，那么整个三元组都可以删去。然后再在某个三元组上二分，得到决策区间，将这个三元组留下前半部分并加入这次的位置的新三元组。
[NOI2009] 诗人小G
点击查看代码
#include
using namespace std;
long long t,n,l,p;
long long sum[100005];
long double dp[100005];
int ql[100005],qr[109005],top,ed;
int pre[100005];
int stk[100005],tp;
char s[100005][33];
inline long double ksm(long double a,long long b){
long double res=1;
while(b){
if(b&1)res*=a;
a*=a;b>>=1;
}
return res;
}
inline long double calc(int i,int j){
return dp[j]+ksm(abs(sum[i]-sum[j]-1-l),p);
}
inline int bound(int i,int j,int x){
int l=x,r=n+1;
while(l<=r){
int mid=(l+r)>>1;
if(calc(mid,i)<=calc(mid,j))r=mid-1;
else l=mid+1;
}
return l;
}
int main(){
scanf("%lld",&t);
while(t--){
scanf("%lld%lld%lld",&n,&l,&p);
for(int i=1;i<=n;i++){
scanf("%s",s[i]);
sum[i]=sum[i-1]+strlen(s[i])+1;
}
tp=top=ed=0;qr[top]=n;
for(int i=1;i<=n;i++){
while(top=bound(i,ql[ed],qr[ed-2]+1))ed--;
qr[ed]=bound(i,ql[ed],qr[ed-1]+1);ql[++ed]=i;
}
if(dp[n]>1e18){
puts("Too hard to arrange");
puts("--------------------");
continue;
}
printf("%.0Lf\n",dp[n]);
for(int i=stk[tp]=n;i;stk[++tp]=i=pre[i]);
for(int i=tp;i;i--){
for(int j=stk[i]+1;j<=stk[i-1];j++){
if(j!=stk[i-1])printf("%s ",s[j]);
else printf("%s\n",s[j]);
}
}
puts("--------------------");
}
return 0;
}
[IOI2000] 邮局 加强版
点击查看代码
```cpp #includePowered by .NET 6 on Kubernetes