单调队列优化Dp
#写在前面##最大子序和----c++版
##旅行问题----c++版
##烽火传递----c++版
##绿色通道----c++版
##修剪草坪----c++版
##理想的正方形----c++版
#写在前面
基础数据结构里有滑动窗口
从正确的朴素dp再到优化
多重背包问题3就是一道单调队列优化的Dp问题
##最大子序和
https://www.acwing.com/problem/content/137/
----c++版
#include<iostream>
#include<algorithm>
using namespace std
;
#include<cstring>
const int N
=300010, inf
=1e9;
int n
,m
;
int s
[N
],q
[N
];
int main(){
scanf("%d%d", &n
, &m
);
for(int i
=1;i
<=n
;i
++){
scanf("%d", &s
[i
]);
s
[i
]+=s
[i
-1];
}
int hh
=0, tt
=0;
int res
=-inf
;
for(int i
=1; i
<=n
;i
++){
if(q
[hh
]<i
-m
)hh
++;
res
=max(res
, s
[i
]-s
[q
[hh
]]);
while(hh
<=tt
&&s
[q
[tt
]]>=s
[i
])tt
--;
q
[++tt
]=i
;
}
printf("%d\n", res
);
return 0;
}
##旅行问题
https://www.acwing.com/problem/content/1090/
----c++版
#include<iostream>
#include<algorithm>
using namespace std
;
typedef long long ll
;
const int N
=2e6+10;
int n
;
int o
[N
], d
[N
];
ll s
[N
];
bool ans
[N
];
int q
[N
*2];
int main(){
scanf("%d", &n
);
for(int i
=1; i
<=n
; i
++)scanf("%d%d", &o
[i
], &d
[i
]);
for(int i
=1;i
<=n
;i
++) s
[i
]=s
[i
+n
]=o
[i
]-d
[i
];
for(int i
=1;i
<=n
*2;i
++) s
[i
] += s
[i
-1];
int hh
=0, tt
=-1;
for(int i
=n
*2; i
; i
--){
if(hh
<=tt
&&q
[hh
]>=i
+n
)hh
++;
while(hh
<=tt
&& s
[q
[tt
]]>=s
[i
])tt
--;
q
[++tt
]=i
;
if(i
<=n
){
if(s
[q
[hh
]]>=s
[i
-1])ans
[i
]=true;
}
}
d
[0]=d
[n
];
for(int i
=1;i
<=n
; i
++)s
[i
]=s
[i
+n
]=o
[i
]-d
[i
-1];
for(int i
=1; i
<=n
*2;i
++)s
[i
]+=s
[i
-1];
hh
=0,tt
=-1;
for(int i
=1; i
<=n
*2; i
++){
if(hh
<=tt
&& q
[hh
]<i
-n
)hh
++;
if(i
>n
){
if(s
[q
[hh
]]<=s
[i
])ans
[i
-n
]=true;
}
while(hh
<=tt
&&s
[q
[tt
]]<=s
[i
])tt
--;
q
[++tt
]=i
;
}
for(int i
=1;i
<=n
;i
++)
if(ans
[i
])puts("TAK");
else puts("NIE");
return 0;
}
##烽火传递
https://www.acwing.com/problem/content/1091/
由于必须要在区间中选一个，状态转移方程才能这样写，状态才能定义为 ”选第i个“
----c++版
#include<iostream>
#include<algorithm>
using namespace std
;
const int N
=200010;
int n
,m
;
int w
[N
];
int f
[N
];
int q
[N
];
int main(){
scanf("%d%d", &n
, &m
);
for(int i
=1; i
<=n
; i
++)scanf("%d", &w
[i
]);
int hh
=0, tt
=0;
for(int i
=1; i
<=n
; i
++){
if(q
[hh
]<i
-m
)hh
++;
f
[i
]=f
[q
[hh
]]+w
[i
];
while(hh
<=tt
&&f
[q
[tt
]]>=f
[i
])tt
--;
q
[++tt
]=i
;
}
int res
=1e9;
for(int i
=n
-m
+1; i
<=n
; i
++)res
=min(res
, f
[i
]);
printf("%d", res
);
return 0;
}
##绿色通道
https://www.acwing.com/problem/content/1092/
----c++版
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std
;
const int N
=50010;
int n
,m
;
int w
[N
];
int q
[N
], f
[N
];
bool check(int limit
){
int hh
=0,tt
=0;
for(int i
=1;i
<=n
;i
++){
if(q
[hh
]<i
-limit
-1)hh
++;
f
[i
] = f
[q
[hh
]]+w
[i
];
while(hh
<=tt
&& f
[q
[tt
]]>=f
[i
])tt
--;
q
[++tt
]=i
;
}
int res
=1e9;
for(int i
=n
-limit
; i
<=n
; i
++) res
=min(res
, f
[i
]);
return res
<=m
;
}
int main(){
cin
>>n
>>m
;
for(int i
=1; i
<=n
; i
++)cin
>>w
[i
];
int l
=0,r
=n
;
while(l
<r
){
int mid
=l
+r
>>1;
if(check(mid
))r
=mid
;
else l
=mid
+1;
}
printf("%d", r
);
return 0;
}
##修剪草坪
https://www.acwing.com/problem/content/1089/
----c++版
#include<iostream>
#include<algorithm>
using namespace std
;
const int N
=100100;
typedef long long ll
;
int n
,m
;
ll s
[N
];
ll f
[N
];
int q
[N
];
ll
g(int i
){
return f
[i
-1]-s
[i
];
}
int main(){
scanf("%d%d", &n
,&m
);
for(int i
=1; i
<=n
; i
++){
scanf("%lld", &s
[i
]);
s
[i
]+=s
[i
-1];
}
int hh
=0, tt
=0;
for(int i
=1; i
<=n
; i
++){
if(q
[hh
]<i
-m
)hh
++;
f
[i
]=max(f
[i
-1], g(q
[hh
])+s
[i
]);
while(hh
<=tt
&& g(q
[tt
])<=g(i
))tt
--;
q
[++tt
]=i
;
}
printf("%lld", f
[n
]);
return 0;
}
##理想的正方形
https://www.acwing.com/problem/content/1093/
----c++版
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std
;
const int N
=1010;
int n
,m
,k
;
int w
[N
][N
];
int row_max
[N
][N
], row_min
[N
][N
];
void get_min(int a
[], int b
[], int tot
){
int hh
= 0, tt
= -1, q
[N
];
for(int i
=1; i
<=tot
; i
++){
if(hh
<=tt
&& q
[hh
]<=i
-k
)hh
++;
while(hh
<=tt
&&a
[q
[tt
]]>=a
[i
])tt
--;
q
[++tt
]=i
;
b
[i
]=a
[q
[hh
]];
}
}
void get_max(int a
[], int b
[], int tot
){
int hh
= 0, tt
= -1, q
[N
];
for(int i
=1; i
<=tot
; i
++){
if(hh
<=tt
&& q
[hh
]<=i
-k
)hh
++;
while(hh
<=tt
&&a
[q
[tt
]]<=a
[i
])tt
--;
q
[++tt
]=i
;
b
[i
]=a
[q
[hh
]];
}
}
int main(){
scanf("%d%d%d", &n
, &m
, &k
);
for(int i
=1; i
<=n
; i
++)
for(int j
=1; j
<=m
; j
++)
scanf("%d", &w
[i
][j
]);
for(int i
=1; i
<=n
; i
++){
get_min(w
[i
], row_min
[i
], m
);
get_max(w
[i
], row_max
[i
], m
);
}
int res
=1e9;
int a
[N
], b
[N
], c
[N
];
for(int i
=k
; i
<=m
; i
++){
for(int j
=1; j
<=n
; j
++)a
[j
] = row_min
[j
][i
];
get_min(a
, b
, n
);
for(int j
=1; j
<=n
; j
++)a
[j
] = row_max
[j
][i
];
get_max(a
, c
, n
);
for(int j
=k
; j
<=n
; j
++)res
= min(res
, c
[j
]-b
[j
]);
}
printf("%d", res
);
return 0;
}
