DPHARD
2024-04-07 22:42:16
此篇收集各类DP题。
《1D1D动态规划优化初步》的3个模型
1. f[x] = min(f[i]+w[i, x]), i < x且w[i, x]满足单调性(即w[i, j]+w[i+1, j+1] <= w[i, j+1]+w[i+1, j]，下四边形同)
2. f[x] = min(g[i])+w[x], b[x] <= i < x, b[x]单调递增
3. f[i]=max{x[j]*a[i]+y[j]*b[i]} = b[i]*max{a[i]/b[i]*x[j]+y[j]}，变成了斜率优化
一. 四边形不等式
eg. Hiho1621：超市规划
dp[i, j] = min{ dp[k, j-1] + w[k+1, i] }, 把长度为i的序列切分成j段，可糙猛快分治
dp[i, j] = min{ dp[i, k-1] + dp[k, j] + w[i, j] }, 合并[i, j]区间。注意决策点应该在哪些范围之内单调，比如对于区间dp的方程来说，决策点的单调范围就应该是行号小于等于列号的那一部分。
以上形式通常情况下w会满足四边形不等式，会使得决策opt[i, j] 与 opt[i, j-1], opt[i-1, j]满足单调性。
#include<bits/stdc++.h>
using namespace std;
const int N = ;
const double inf = 1e17;
double dp[N][N], c[N][N];
double a[N], sum1[N], sum2[N], opt[N][N];
int main()
{
int n, m;
scanf("%d%d",&n,&m);
for(int i = ; i <= n; i++)
scanf("%lf", a+i);
sort(a+, a+n+);
for(int i = ; i <= n; i++) {
sum1[i] = sum1[i-]+a[i];
sum2[i] = sum2[i-]+a[i]*a[i];
}
for(int i = ; i <= n; i++)
for(int j = i+; j <= n; j++){
double mid = (sum1[j]-sum1[i-])/(j-i+);
c[i][j] = (sum2[j]-sum2[i-])+(j-i+)*mid*mid-*mid*(sum1[j]-sum1[i-]);
}
for(int i = ; i <= m; i++)
for(int j = ; j <= n; j++)
dp[i][j] = inf;
for(int i = ; i <= n; i++) dp[][i] = c[][i];
for(int i = ; i <= m; i++){
opt[i][n+] = n;
for(int j = n; j >= ; j--){
for(int k = opt[i-][j]; k <= opt[i][j+]; k++)
if(dp[i][j] > dp[i-][k]+c[k+][j]){
opt[i][j] = k;
dp[i][j] = dp[i-][k]+c[k+][j];
}
}
}
printf("%.3lf\n", dp[m][n]);
return ;
}
决策单调且不要求在线的糙快猛优化方法（for内写成i <= dr && i < m会有bug，m = 1的时候，循环无法进入，导致f[1]值无穷大）
//个人感觉适用于状态数为二维的dp, 下一行(列)由前一行(列)推出, 且满足决策单调性
void solve(int l, int r, int dl, int dr) {
if(l > r) return ;
int m = (l+r) >> , dm;
for(int i = dl; i <= dr; i++) {
if(i更新f[m]更优) {
dm = i;
更新f[m];
}
}
solve(l, m-, dl, dm), solve(m+, r, dm, dr);
}
基于决策单调的糙猛快分治
#include<bits/stdc++.h>
using namespace std;
const int N = ;
const double inf = 1e17;
double dp[N][N], c[N][N];
double a[N], sum1[N], sum2[N], opt[N][N];
void solve(double *f1, double *f2, int l, int r, int dl, int dr) {
if(l > r) return ;
int m = (l+r) >> , dm;
for(int i = dl; i <= dr; i++) {
if(f1[i]+c[i+][m] < f2[m])
f2[m] = f1[i]+c[i+][m], dm = i;
}
solve(f1, f2, l, m-, dl, dm);
solve(f1, f2, m+, r, dm, dr);
}
int main() {
int n, m;
scanf("%d%d",&n,&m);
for(int i = ; i <= n; i++)
scanf("%lf", a+i);
sort(a+, a+n+);
for(int i = ; i <= n; i++) {
sum1[i] = sum1[i-]+a[i];
sum2[i] = sum2[i-]+a[i]*a[i];
}
for(int i = ; i <= n; i++)
for(int j = i+; j <= n; j++){
double mid = (sum1[j]-sum1[i-])/(j-i+);
c[i][j] = (sum2[j]-sum2[i-])+(j-i+)*mid*mid-*mid*(sum1[j]-sum1[i-]);
} for(int i = ; i <= m; i++)
for(int j = ; j <= n; j++)
dp[i][j] = inf;
for(int i = ; i <= n; i++) dp[][i] = c[][i];
for(int i = ; i <= m; i++)
solve(dp[i-], dp[i], , n, , n);
printf("%.3f\n", dp[m][n]);
return ;
}
eg. hiho1933
四边形不等式优化
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+; long long a[N], sum[N], dp[N][];
int opt[N][]; long long get_sum(int l, int r) {
int m = (l+r) >> ;
long long ans1 = a[m]*(m-l)-(sum[m-]-sum[l-]);
long long ans2 = (sum[r]-sum[m])-a[m]*(r-m);
return ans1+ans2;
} int main() {
int n, k; cin >> n >> k;
for(int i = , x, y; i <= n; i++) {
cin >> x >> y;
a[i] = y;
}
sort(a+, a+n+);
for(int i = ; i <= n; i++) sum[i] = sum[i-]+a[i]; memset(dp, 0x3f, sizeof(dp));
for(int i = ; i <= k; i++) dp[][i] = ; //这里i <= k写成了i <= n, 一直WA
for(int i = ; i <= n; i++) {
opt[i][k+] = n;
for(int j = k; j; j--) {
for(int kk = opt[i-][j]; kk <= opt[i][j+]; kk++) {
long long tmp = dp[kk][j-]+get_sum(kk+, i);
if(tmp < dp[i][j])
dp[i][j] = tmp, opt[i][j] = kk;
}
}
}
cout << dp[n][k] << endl;
return ;
}
基于决策单调的糙猛快分治
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+; long long a[N], sum[N], dp[][N]; long long get_sum(int l, int r) {
if(l >= r) return ;
int m = (l+r) >> ;
long long ans1 = a[m]*(m-l)-(sum[m-]-sum[l-]);
long long ans2 = (sum[r]-sum[m])-a[m]*(r-m);
return ans1+ans2;
} void solve(long long *f1, long long *f2, int l, int r, int dl, int dr) {
if(l > r) return ;
int m = (l+r) >> , dm;
for(int i = dl; i <= dr; i++) {
long long tmp = f1[i]+get_sum(i+, m);
if(tmp < f2[m]) {
f2[m] = tmp;
dm = i;
}
}
solve(f1, f2, l, m-, dl, dm);
solve(f1, f2, m+, r, dm, dr);
} int main() {
int n, k; cin >> n >> k;
for(int i = , x, y; i <= n; i++) {
cin >> x >> y;
a[i] = y;
}
sort(a+, a+n+);
for(int i = ; i <= n; i++) sum[i] = sum[i-]+a[i]; for(int i = ; i <= n; i++)
dp[][i] = get_sum(, i);
for(int i = ; i <= k; i++) {
bool now = (i&);
memset(dp[now], 0x3f, sizeof(dp[now]));
solve(dp[!now], dp[now], , n, , n);
}
cout << dp[k&][n] << endl;
return ;
}
二. 斜率优化
eg. HDU3507
f[i] = min(f[j]+(s[i]-s[j])²)+M
= min(f[j]+s[j]²-2s[i]s[j])+M+s[i]²
= min(kx+b)+M+s[i]², 其中k = -2s[j], b = f[j]+s[j]², x = s[i]
注：你也可看作k = 2s[i], x = s[j], y = f[j]+s[j]², f[i] = min(y-kx), k是定值，
则求k为定值的直线y = kx+b的最小截距。脑补画面，将斜率为k的直线移到最下端....
个人认为将整个min里的值当作y，当前已知值作为自变量比较好...
其它题目的变形：f[i]=max{x[j]*a[i]+y[j]*b[i]} = b[i]*max{a[i]/b[i]*x[j]+y[j]}
因为求min，所以维护倒U形(上凸)
因为k递减，x递增，所以用单调队列维护即可，队列内直线按k递减排序，维护倒U形。
代码区===待填===
ps.
如果x无序，则每次二分查找;
如果k无序，可以用set维护，插入的时候erase掉两侧不符合的直线;
如果x, k都无序，可以用set按k值排序维护直线，查找的时候再二分k，lowerbound计算在哪条斜率的直线上(判断x值是否在该直线的两端点内，不在则继续二分)
三、WQS二分
作用就是题目给了一个选物品的限制条件，要求刚好选m个，让你最大化(最小化)权值，然后其特点就是当选的物品越多的时候权值越大（越小）。
http://codeforces.com/blog/entry/49691
https://www.cnblogs.com/HocRiser/p/9834069.html
https://www.cnblogs.com/flashhu/p/9480669.html
https://www.cnblogs.com/CreeperLKF/p/9045491.html
=================================================================================================
区间dp
括号dp：
hihocoder1891：有多少种填充*的方案使得括号匹配？
#include <bits/stdc++.h> #define ll long long
#define ull unsigned long long
#define st first
#define nd second
#define pii pair<int, int>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tiii tuple<int, int, int>
#define pw(x) ((1LL)<<(x))
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sqr(x) ((x)*(x))
#define SIZE(A) ((int)(A.size()))
#define LENGTH(A) ((int)(A.length()))
#define FIN freopen("A.in","r",stdin);
#define FOUT freopen("A.out","w",stdout);
using namespace std;
/***********/ template<typename T>
bool scan (T &ret) {
char c;
int sgn;
if (c = getchar(), c == EOF) return ; //EOF
while (c != '-' && (c < '' || c > '') ) c = getchar();
sgn = (c == '-') ? - : ;
ret = (c == '-') ? : (c - '');
while (c = getchar(), c >= '' && c <= '') ret = ret * + (c - '');
ret *= sgn;
return ;
}
template<typename N,typename PN>inline N flo(N a,PN b){return a>=?a/b:-((-a-)/b)-;}
template<typename N,typename PN>inline N cei(N a,PN b){return a>?(a-)/b+:-(-a/b);}
template<typename T>inline int sgn(T a) {return a>?:(a<?-:);}
template<class T> int countbit(const T &n) { return (n==)?:(+countbit(n&(n-))); }
template <class T1, class T2>
bool gmax(T1 &a, const T2 &b) { return a < b? a = b, :;}
template <class T1, class T2>
bool gmin(T1 &a, const T2 &b) { return a > b? a = b, :;}
template <class T> inline T lowbit(T x) {return x&(-x);} template<class T1, class T2>
ostream& operator <<(ostream &out, pair<T1, T2> p) {
return out << "(" << p.st << ", " << p.nd << ")";
}
template<class A, class B, class C>
ostream& operator <<(ostream &out, tuple<A, B, C> t) {
return out << "(" << get<>(t) << ", " << get<>(t) << ", " << get<>(t) << ")";
}
template<class T>
ostream& operator <<(ostream &out, vector<T> vec) {
out << "("; for(auto &x: vec) out << x << ", "; return out << ")";
}
void testTle(int &a){
while() a = a*(ll)a%;
}
const ll inf = 0x3f3f3f3f;
const ll INF = 1e17;
const int mod = ;;
const double eps = 1e-;
const int N = +;
const double pi = acos(-1.0); /***********/ char s[N];
long long dp[][N];
void add(long long &x, long long y) {
x += y;
if(x >= mod) x %= mod;
}
int main() {
scanf("%s", s);
int tag = , modify = , base = , l = ;
dp[][] = ;
for(int i = ; s[i]; i++) {
if(s[i] == '(')
base++;
else if(s[i] == ')') {
if(base) base--;
else {
l--;
if(l == ) { puts(""); return ; }
modify++;
}
}
else {
if(modify) {
tag = !tag;
for(int j = ; j < l; j++)
dp[tag][j] = dp[!tag][j+modify];
modify = ;
}
tag = !tag;
if(base) {
memset(dp[tag], , sizeof(long long)*(l+));
for(int j = ; j < l; j++) {
add(dp[tag][j], dp[!tag][j]);
add(dp[tag][j+], dp[!tag][j]);
}
base--, l += ;
}
else {
memset(dp[tag], , sizeof(long long)*(l+));
for(int j = ; j < l; j++) {
if(j) add(dp[tag][j-], dp[!tag][j]);
add(dp[tag][j+], dp[!tag][j]);
}
l++;
}
}
}
if(modify) {
tag = !tag;
for(int j = ; j < l; j++)
dp[tag][j] = dp[!tag][j+modify];
modify = ;
}
printf("%lld\n", base? : dp[tag][]);
return ;
}
最新文章
- A New Beginning
- ASP.NET WebAPI 11 参数验证
- Activity启动方式
- unity, ugui input field
- UVA 10066 The Twin Towers（LCS）
- Java学习笔记--对象克隆
- power oj 1557种树[二进制状压DP]
- C++设计模式-Singleton单例模式
- 机器学习:形如抛物线的散点图在python和R中的非线性回归拟合方法
- linux下实时监测命令运行结果工具：watch
- xstream实现对象的序列化和反序列化（Java）
- Servlet（五）：请求转发和重定向
- vue打包后接口报错
- spring-session+Redis实现Session共享
- HTML load事件和DOMCOntentLoaded事件
- 如何写好.babelrc？Babel的presets和plugins配置解析
- 在PE32位下安装64位2003、2008系统
- CentOS 7安装GitLab 11.4.5
- VS2013下.Net Framework4配置FineUI4.14
- centos 挂载u盘