称满足条件的序列为"波动序列"
性质1: 如果一个波动序列中 i 和 i+1 不相邻, 则交换这两个数后仍然是波动序列
性质2: 将一个波动序列反转, 翻转后仍然是波动序列
设 f[i][j] 表示由 1~i 的数构成的波动序列, 第一个数为 j 且为山峰的方案数
如果 j 与 j-1 不相邻, 则交换这两个数后仍然满足是波动序列: f[i][j]←f[i][j-1]
如果 j 与 j-1 相邻, 则 j-1 必定为山谷, 且位于 [2,i] 的数在 [1,j)∪(j,i] 中
此时将 (j,i] 中的数均减 1 就变成将 i-1 个数排成第一个数 j-1 为山谷的方案数
将这个序列反转 (每个数变为i减去自己) 得到第一个数为 i-j+1 的方案数
点击查看代码
#include <stdio.h>
const int N = 4205;
int n, mod, f[2][N], res;
int main() {
scanf("%d%d", &n, &mod);
f[0][2] = 1; // f[2][2] = 1: [2,1]
for(int i = 3; i <= n; i ++)
for(int j = 2; j <= i; j ++)
f[i&1][j] = (f[i&1][j-1] + f[(i-1)&1][i-j+1]) % mod;
for(int i = 2; i <= n; i ++) (res += f[n&1][i]) %= mod;
printf("%d\n", (res << 1) % mod);
return 0;
}
USACO07NOVTelephone Wire G
给出若干棵树的高度，你可以进行一种操作：把某棵树增高h，花费为hh。
操作完成后连线，两棵树间花费为高度差定值c。
求两种花费加和最小值。
过题之后，又写了两种优化后的代码
点击查看代码一
#include <math.h> // 朴素dp:f[i][j]表示将i的高度变为j的最小花费
#include <stdio.h> // f[i][j]=f[i-1][k]+|j-k|*c+(j-h[i])**2
#include <string.h> // j单调时k单调
#include <algorithm>
const int N = 1e5 + 2;
int n, m, c, h[N], res = 0x3f3f3f3f, f[2][102]; // 滚动数组
int main() {
scanf("%d%d", &n, &c);
for(int i = 1; i <= n; i ++) scanf("%d", h + i), m = std::max(m, h[i]);
for(int i = h[1]; i <= m; i ++) f[1][i] = (i - h[1]) * (i - h[1]);
for(int i = 2; i <= n; i ++)
for(int k = h[i], j = h[i-1]; k <= m; k ++) {
while(j < m && f[(i-1)&1][j] + abs(k - j) * c > f[(i-1)&1][j+1] + abs(k - (j+1)) * c) j ++;
f[i&1][k] = f[(i-1)&1][j] + abs(k - j) * c + (k - h[i]) * (k - h[i]);
}
for(int j = h[n]; j <= m; j ++) res = std::min(res, f[n&1][j]);
printf("%d\n", res);
return 0;
}
点击查看代码二
#include <math.h> // 朴素dp:f[i][j]表示将i的高度变为j的最小花费
#include <stdio.h> // f[i][j]=f[i-1][k]+|j-k|*c+(j-h[i])**2
#include <string.h> // 将绝对值拆开, 用变量维护f[i-1][k]+-c*k即可
#include <algorithm> // 正着反着都要循环一遍
const int N = 1e5 + 2;
int n, m, c, h[N], res = 0x3f3f3f3f, f[2][102]; // 滚动数组
int main() {
scanf("%d%d", &n, &c);
for(int i = 1; i <= n; i ++) scanf("%d", h + i), m = std::max(m, h[i]);
memset(f[1], 0x3f, sizeof(f[1]));
for(int i = h[1]; i <= m; i ++) f[1][i] = (i - h[1]) * (i - h[1]);
for(int i = 2; i <= n; i ++) {
memset(f[i&1], 0x3f, sizeof(f[i&1]));
int minn = 0x3f3f3f3f;
for(int j = 1; j < h[i]; j ++) minn = std::min(minn, f[(i-1)&1][j] - c * j);
for(int j = h[i]; j <= m; j ++)
minn = std::min(minn, f[(i-1)&1][j] - c * j),
f[i&1][j] = std::min(f[i&1][j], minn + c * j + (j - h[i]) * (j - h[i]));
minn = 0x3f3f3f3f;
for(int j = m; j >= h[i]; j --)
minn = std::min(minn, f[(i-1)&1][j] + c * j),
f[i&1][j] = std::min(f[i&1][j], minn - c * j + (j - h[i]) * (j - h[i]));
}
for(int j = h[n]; j <= m; j ++) res = std::min(res, f[n&1][j]);
printf("%d\n", res);
return 0;
}