1.背包
这个博客基本总结的比较全了。
2.斜率优化
HDU 3507
暴力 f[i]=min{f[j]+s[i]^2+s[j]^2-s[i]*s[j]+W}
f[i]=f[j]+s[i]^2+s[j]^2-s[i]*s[j]+W
假设j>k 当j比k优时 有f[j]+s[i]^2+s[j]^2-s[i]s[j]+W <= f[k]+s[i]^2+s[k]^2-s[i]s[k]+W
化简有 ( (f[j]+s[j]^2)-(f[k]+s[k]^2) )/(s[j]-s[k])<=2*s[i]
令 F[x]=f[x]+s[x]^2 K[k,j]表示k->j构成的斜率 搞成点 (F[x],s[x])
则最后可以转移的集合一定是一个下凸包
反证：如果存在一个上凸包 k j i 若K[k,j]>K[j,i]>2*s[i] 则j比i好 k比j好 其他情况同理
而且这个凸包有单调性 也就是在所有 K<=2*s[i]的点构成的直线中 最右边的点是最优的
可以二分找到最优值
#include<bits/stdc++.h>
#define ll long long
#define maxn 500010
using namespace std;
ll n, m, q[maxn], hea, tai;
ll f[maxn], s[maxn];
ll F(ll x) {
return f[x] + s[x] * s[x];
}
ll cal(ll i, ll j) {
return f[j] + (s[i] - s[j]) * (s[i] - s[j]) + m;
}
bool K_big(ll i, ll x) {
return F(q[i]) - F(q[i - 1]) <= 2 * s[x] * (s[q[i]] - s[q[i - 1]]);
}
bool K_bg(ll a1, ll b1, ll a2, ll b2) {
return (F(a1) - F(b1)) * (s[a2] - s[b2]) >= (F(a2) - F(b2)) * (s[a1] - s[b1]);
}
int main() {
while (~scanf("%lld%lld", &n, &m)) {
hea = tai = 0;
for (ll i = 1; i <= n; i++) {
scanf("%lld", &s[i]);
s[i] = s[i - 1] + s[i];
}
for (ll i = 1; i <= n; i++) {
f[i] = cal(i, 0);
while (tai - hea > 1 && K_big(hea + 2, i))hea++;
f[i] = min(f[i], cal(i, q[hea + 1]));
while (tai - hea > 1 && K_bg(q[tai], q[tai - 1], i, q[tai]))tai--;
q[++tai] = i;
}
printf("%lld\n", f[n]);
}
return 0;
}然后发现2*s[i]是单调的，也就是每次二分找到的mid也是单调的，就可以不用二分了，直接单调队列就可以O(1)的转移了。
#include<bits/stdc++.h>
#define ll long long
#define maxn 500010
using namespace std;
ll n, m, q[maxn], hea, tai;
ll f[maxn], s[maxn];
ll F(ll x) {
return f[x] + s[x] * s[x];
}
ll cal(ll i, ll j) {
return f[j] + (s[i] - s[j]) * (s[i] - s[j]) + m;
}
bool K_big(ll i, ll x) {
return F(q[i]) - F(q[i - 1]) <= 2 * s[x] * (s[q[i]] - s[q[i - 1]]);
}
bool K_bg(ll a1, ll b1, ll a2, ll b2) {
return (F(a1) - F(b1)) * (s[a2] - s[b2]) >= (F(a2) - F(b2)) * (s[a1] - s[b1]);
}
int main() {
while (~scanf("%lld%lld", &n, &m)) {
hea = tai = 0;
for (ll i = 1; i <= n; i++) {
scanf("%lld", &s[i]);
s[i] = s[i - 1] + s[i];
}
for (ll i = 1; i <= n; i++) {
f[i] = cal(i, 0);
while (tai - hea > 1 && K_big(hea + 2, i))hea++;
f[i] = min(f[i], cal(i, q[hea + 1]));
while (tai - hea > 1 && K_bg(q[tai], q[tai - 1], i, q[tai]))tai--;
q[++tai] = i;
}
printf("%lld\n", f[n]);
}
return 0;
}暑假牛客最后一场最后一题
/*
这题比较斜率的时候如果改成不丢失精度的*好像爆longlong 需要int128
当然保留除法精度也没啥问题
*/
#include<bits/stdc++.h>
#define ll long long
#define db long double
#define maxn 5010
using namespace std;
ll n, m, f[maxn][maxn], s[maxn], ss[maxn], q[maxn], hea, tai, p;
const db One = 1.0;
struct node {
ll h, w;
} a[maxn];
ll cmp(node a, node b) {
return a.h > b.h;
}
ll F(ll x) {
return f[p - 1][x] - s[x];
}
ll cal(ll j, ll k) {
return f[p - 1][k] + s[j] - s[k] - (ss[j] - ss[k]) * a[j].h;
}
bool K_big(ll i, ll x) {
return One * (F(q[i]) - F(q[i - 1])) / (ss[q[i]] - ss[q[i - 1]]) <= -a[x].h;
}
bool K_bg(ll a1, ll b1, ll a2, ll b2) {
return One * (F(a1) - F(b1)) / (ss[a1] - ss[b1]) >= One * (F(a2) - F(b2)) / (ss[a2] - ss[b2]);
}
int main() {
scanf("%lld%lld", &n, &m);
for (ll i = 1; i <= n; i++)
scanf("%lld%lld", &a[i].w, &a[i].h);
sort(a + 1, a + 1 + n, cmp);
for (ll i = 1; i <= n; i++) {
s[i] = s[i - 1] + a[i].h * a[i].w;
ss[i] = ss[i - 1] + a[i].w;
}
memset(f, 127 / 3, sizeof(f));
f[0][0] = 0;
for (ll i = 1; i <= m; i++) {
p = i;
hea = tai = 0;
for (ll j = i; j <= n; j++) {
f[i][j] = cal(j, i - 1);
while (tai - hea > 1 && K_big(hea + 2, j))hea++;
f[i][j] = min(f[i][j], cal(j, q[hea + 1]));
while (tai - hea > 1 && K_bg(q[tai], q[tai - 1], j, q[tai - 1]))tai--;
q[++tai] = j;
}
}
printf("%lld\n", f[m][n]);
return 0;
}3.决策单调
首先比较经典的就是四边形不等式优化dp
证明的话，大概就是先证costok，然后dpok，然后就是决策单调。
当然了，打比赛的时候是不可能证的，就打表就完事了。
#include<bits/stdc++.h>
#define maxn 210
using namespace std;
int n, a[maxn], ss[maxn], f[maxn][maxn], g[maxn][maxn], s[maxn][maxn];
int main() {
scanf("%d", &n);
memset(f, 127 / 3, sizeof(f));
memset(g, -127 / 3, sizeof(g));
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a[i + n] = a[i];
}
int a1 = 1e9, a2 = 0;
n = n * 2;
for (int i = 1; i <= n; i++) {
ss[i] = ss[i - 1] + a[i];
f[i][i] = 0, g[i][i] = 0, s[i][i] = i;
}
for (int i = n - 1; i >= 1; i--)
for (int j = i + 1; j <= n; j++) {
for (int k = s[i][j - 1]; k <= s[i + 1][j]; k++)
if (f[i][j] > f[i][k] + f[k + 1][j] + ss[j] - ss[i - 1]) {
f[i][j] = f[i][k] + f[k + 1][j] + ss[j] - ss[i - 1];
s[i][j] = k;
}
if (j - i + 1 == n / 2)a1 = min(a1, f[i][j]);
// printf("%d %d %d\n",i,j,s[i][j]);
}
for (int i = n - 1; i >= 1; i--)
for (int j = i + 1; j <= n; j++) {
for (int k = i; k <j; k++)
if (g[i][j] < g[i][k] + g[k + 1][j] + ss[j] - ss[i - 1]) {
g[i][j] = g[i][k] + g[k + 1][j] + ss[j] - ss[i - 1];
s[i][j] = k;
}
if (j - i + 1 == n / 2)a2 = max(a2, g[i][j]);
// printf("%d %d %d\n",i,j,s[i][j]);
}
printf("%d\n%d\n", a1, a2);
return 0;
}前几天的训练里面有一个扔鸡蛋的dp，怎么想都不知道怎么优化，最后打表可以看出来转移的单调。
#include<bits/stdc++.h>
#define mod 100000073
#define maxn 5000010
using namespace std;
int f[maxn], a[maxn], b[maxn], s[maxn], ss[maxn];
int cal(int i, int j) {
return max(j - 1, f[i - j]);
}
void pre(int n) {
f[1] = a[1] = b[1] = s[0] = s[1] = ss[0] = 1, ss[1] = 2;
for (int i = 2; i <= n; i++) {
for (b[i] = b[i - 1]; b[i] < i && cal(i, b[i] + 1) <= cal(i, b[i]); b[i]++);
f[i] = cal(i, b[i]) + 1;
for (a[i] = a[i - 1]; a[i] < i && cal(i, a[i]) >= f[i]; a[i]++);
for (; a[i] > 1 && cal(i, a[i] - 1) < f[i]; a[i]--);
s[i] = (ss[i - a[i]] - ss[i - b[i] - 1] + mod) % mod;
ss[i] = (ss[i - 1] + s[i]) % mod;
}
}
int main() {
pre(5000000);
int x, y;
while (~scanf("%d%d", &x, &y))
printf("%d %d\n", f[y - x + 1], s[y - x + 1]);
return 0;
}
京公网安备 11010502036488号