第1题 Luogu P2734 游戏 A Game
Luogu P2734 游戏 A Game
题意：有一个序列，有两个玩家，每个玩家用最优策略在两端拿数，求先手拿到数字和的最大值。
解：由于两个玩家都采取最优策略，我们设$dp(i,j)$为区间$[i,j]$先手能得到的最优解。然后方程为$dp(i,j)=max(sum(i,j) - dp(i + 1, j), sum(i,j)-dp(i,j-1))$。$sum$是这一段的和。原理是区间DP的原理，整个区间$[i,j]$的先手，在$(i,j],[i,j)$是后手，$dp(i + 1, j), dp(i,j-1)$是$(i,j],[i,j)$的先手最优值
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int n, a[105], dp[105][105], sum[105][105];
void clean() {
ms(dp, 0);
}
int solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), dp[i][i] = a[i];
for (int i = 1; i <= n; i++) {
sum[i][i] = a[i];
for (int j = i + 1; j <= n; j++) sum[i][j] = sum[i][j - 1] + a[j];
}
for (int i = n; i; i--) {
for (int j = i + 1; j <= n; j++) {
dp[i][j] = max(sum[i][j] - dp[i + 1][j], sum[i][j] - dp[i][j - 1]);
}
}
printf("%d %d\n", dp[1][n], sum[1][n] - dp[1][n]);
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}
第2题 Luogu P3800 Power收集
Luogu P3800 Power收集
题意：$N$行$M$列的格子，某些点有一些权值，每秒钟可以左右移动至多$T$个单位长度(瞬间完成)，每秒必须向下走一行(不能折返)，求一条路径使得权值和最大
解：朴素的DP是$O(n^3)$的，无法通过测试，我们将有权值的点按横坐标排序，然后设$dp(i)$为第$i$个权值点的最优解，那么就有 $dp(i)=dp(j)+v(i)$当且仅当$j$能移动到$i$位置，$v(i)$为$i$权值点的权值
然后初始化第一层的值就行
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
struct data {
int x, y, v, dp;
bool operator < (const data &b) const {
return x < b.x;
}
}v[4000 + 5];
int n, m, k, t;
int abss(int x) {return x > 0 ? x : -x;}
void clean() {}
int solve() {
clean();
for (int i = 1; i <= k; i++) scanf("%d%d%d", &v[i].x, &v[i].y, &v[i].v), v[i].dp = 0;
sort(v + 1, v + 1 + k);
for (int i = 1; ; i++) if (v[i].x != v[i - 1].x && i != 1) break; else v[i].dp = v[i].v;
for (int i = 1; i <= k; i++)
for (int j = 0; j < i; j++)
if (abss(v[i].y - v[j].y) <= t * (v[i].x - v[j].x)) v[i].dp = max(v[i].dp, v[j].dp + v[i].v);
int ans = 0;
for (int i = 1; i <= k; i++) ans = max(ans, v[i].dp);
printf("%d\n", ans);
return 0;
}
int main() {
scanf("%d%d%d%d", &n, &m, &k, &t), solve();
return 0;
}
第3题 Luogu P2889 挤奶的时间Milking Time
Luogu P2889 挤奶的时间Milking Time
题意：有$m$个区间，区间有一个权值，现在要选择一些区间使得权值和最大，选取的每两个区间之间不能覆盖且距离为$r$
解：区间按右端点排序，消除后效性，设$dp(i)$为$i$前$i$个区间的最优值，转移方程
$$dp(i)=max(dp(j)+e(i)|x_i-r \geq y_j)$$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
struct data {
int x, y, v;
bool operator < (const data &b) const {
return y < b.y;
}
}inv[1005];
int n, m, r, dp[1005];
void clean() {
ms(dp, 0);
}
int solve() {
clean();
for (int i = 1; i <= m; i++) scanf("%d%d%d", &inv[i].x, &inv[i].y, &inv[i].v);
sort(inv + 1, inv + 1 + m);
for (int i = 1; i <= m; i++) dp[i] = inv[i].v;
for (int i = 1; i <= m; i++)
for (int j = 1; j < i; j++)
if (inv[i].x - r >= inv[j].y) dp[i] = max(dp[i], dp[j] + inv[i].v);
else dp[i] = max(dp[i], dp[j]);
printf("%d\n", dp[m]);
return 0;
}
int main() {
scanf("%d%d%d", &n, &m, &r), solve();
return 0;
}
第4题 Luogu P2233 [HNOI2002]公交车路线
题意：有一个ABCDEFGH组成的环，求A到E路程为$n$的方案数，要求到达E之前不能到达E
解：遇到环就拆成链，在E点切开，那么成了一条链FGHABCD，到达E点路径总数等于F点和D点的路径总数，把链节点抽象为数字点，设$dp(i,j)$为$j$路程后到$i$点的方案数，则$dp(i,j)=dp(i+1, j-1), dp(i - 1,j-1)$，初始化$dp(4, 0)$为1(从1开始标号)。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MO = 1000;
int n, dp[8][2];
void clean() {}
int solve() {
clean();
dp[4][0] = 1;
int pos = 0;
for (int i = 1; i < n; i++) {
pos ^= 1;
for (int j = 1; j <= 7; j++) dp[j][pos] = (dp[j - 1][pos ^ 1] + dp[j + 1][pos ^ 1]) % MO;
}
printf("%d\n", (dp[1][pos] + dp[7][pos]) % MO);
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}
第5题 Luogu P1373 小a和uim之大逃离
Luogu P1373 小a和uim之大逃离
题意：见上。
解：设$dp(x,y,i,0/1)$为在$(x,y)$小a比uim多$i$毒液的方案数，转移看代码。
知识点：差值状态 DP ，读题要勾画重点
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const int MAXN = 800 + 5, MO = 1000000007;
int n, m, k, a[MAXN][MAXN], dp[MAXN][MAXN][17][2];
void clean() {
ms(dp, 0);
}
int solve() {
clean();
k++;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]), dp[i][j][a[i][j] % k][0] = 1;
int ans = 0;
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= m; y++) {
for (int i = 0; i < k; i++) {
dp[x][y][i][0] = (dp[x][y][i][0] + dp[x - 1][y][((i - a[x][y]) % k + k) % k][1]) % MO;
dp[x][y][i][0] = (dp[x][y][i][0] + dp[x][y - 1][((i - a[x][y]) % k + k) % k][1]) % MO;
dp[x][y][i][1] = (dp[x][y][i][1] + dp[x - 1][y][((i + a[x][y]) % k + k) % k][0]) % MO;
dp[x][y][i][1] = (dp[x][y][i][1] + dp[x][y - 1][((i + a[x][y]) % k + k) % k][0]) % MO;
if (i == 0) ans = (ans + dp[x][y][0][1]) % MO;
//printf("x=%d y=%d i=%d k=0 dp=%d", x, y, i, dp[x][y][i][0]); if (i == 0) printf("&&&\n"); else printf("\n");
//printf("x=%d y=%d i=%d k=1 dp=%d", x, y, i, dp[x][y][i][1]); if (i == 0) printf("&&&\n"); else printf("\n");
}
}
}
printf("%d\n", ans);
return 0;
}
int main() {
scanf("%d%d%d", &n, &m, &k), solve();
return 0;
}
第6题 Luogu P1435 回文字串
Luogu P1435 回文字串
题意：有一个串需要添加最少的字符使得它变为回文串。
解：
1、区间DP。设$dp(i,j)$为区间$[i,j]$变回文的最小值。
转移$dp(i,j)=min(dp(i+1,j-1)|s_i=s_j, dp(i+1,j)+1,dp(i,j - 1)+1)$，直接记忆化搜索即可。(不要忘了直接返回记忆化搜索已经算完的值)
2、因为回文串正读倒读一样，所以正反做公共子序列可以找出回文串部分，然后其余部分就是需要增加来对称的。
代码用方法1。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const int MAXN = 1000 + 5, INF = 1000000000;
int n, dp[MAXN][MAXN];
char s[MAXN];
int DP(int i, int j) {
if (dp[i][j] != INF) return dp[i][j];//别忘了这一步
if (i == j) return dp[i][j] = 0;
if (i > j) return 0;
int ret = INF;
if (s[i] == s[j]) ret = std::min(ret, DP(i + 1, j - 1));
ret = std::min(ret, std::min(DP(i + 1, j) + 1, DP(i, j - 1) + 1));
return dp[i][j] = ret;
}
void clean() {
for (int i = 0; i <= 1001; i++)
for (int j = 0; j <= 1001; j++) dp[i][j] = INF;
}
int solve() {
clean();
n = strlen(s + 1);
DP(1, n);
printf("%d\n", dp[1][n]);
return 0;
}
int main() {
scanf("%s", s + 1), solve();
return 0;
}
第7题 Luogu P1220 关路灯
P1220 关路灯
题意：有$n$盏路灯，老张在$m$处，求老上关完所有电灯的最小所需的功率数。
解：这题看似不满足后效性，但是可以当做区间DP来做。
知识点：如果前…的状态不好用就用区间状态。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const int INF = 1000000000;
int n, c, dp[55][55][2], xi[55], pi[55];
int abss(int x) {return x > 0 ? x : -x;}
int cal(int i, int j, int x, int y) {
return abss(xi[i] - xi[j]) * (pi[x] + pi[n] - pi[y - 1]);
}
int DP(int i, int j, int k) {
if (dp[i][j][k] != INF) return dp[i][j][k];
if (i == j && i == c) return 0;
if (i >= j) return INF;
if (k == 0) dp[i][j][k] = std::min(DP(i + 1, j, 0) + cal(i, i + 1, i, j + 1), DP(i + 1, j, 1) + cal(i, j, i, j + 1));
else dp[i][j][k] = std::min(DP(i, j - 1, 0) + cal(i, j, i - 1, j), DP(i, j - 1, 1) + cal(j - 1, j, i - 1, j));
return dp[i][j][k];
}
void clean() {
for (int i = 0; i <= 51; i++)
for (int j = 0; j <= 51; j++) dp[i][j][0] = dp[i][j][1] = INF;
}
int solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d%d", &xi[i], &pi[i]), pi[i] += pi[i - 1];
DP(1, n, 0), DP(1, n, 1);
/*for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 0; k < 2; k++) printf("i=%d, j=%d, k=%d, dp=%d\n", i, j, k, dp[i][j][k]);*/
printf("%d\n", std::min(dp[1][n][0], dp[1][n][1]));
return 0;
}
int main() {
scanf("%d%d", &n, &c), solve();
return 0;
}
第8题 NOIP 2003 加分二叉树
NOIP 2003 加分二叉树
题意：见上。
解：中序遍历可以将树分开，如果其中一个点是根，那么区间左边就是他的左子树，右边就是他的右子树。所以这题就是一个 区间DP。DP时记录最终是哪个中间值使他最优，递归地分解区间输出前序遍历即可。
知识点：中序遍历可以将树分开，如果其中一个点是根，那么区间左边就是他的左子树，右边就是他的右子树。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
LL n, dp[35][35], a[35], pre[35][35];
LL DP(LL i, LL j) {
if (dp[i][j] >= 0ll) return dp[i][j];
if (i > j) return 1ll;
if (i == j) return pre[i][j] = i, dp[i][j] = a[i];
for (LL k = i; k <= j; k++)
if (dp[i][j] < DP(i, k - 1ll) * DP(k + 1ll, j) + a[k]) dp[i][j] = DP(i, k - 1ll) * DP(k + 1ll, j) + a[k], pre[i][j] = k;
return dp[i][j];
}
void print(LL x, LL y) {
if (pre[x][y]) printf("%lld ", pre[x][y]);
if (x >= y) return ;
print(x, pre[x][y] - 1);
print(pre[x][y] + 1, y);
}
void clean() {
ms(dp, -1);
}
int solve() {
clean();
for (LL i = 1; i <= n; i++) scanf("%lld", &a[i]);
DP(1ll, n);
printf("%lld\n", dp[1][n]);
print(1, n);
return 0;
}
int main() {
scanf("%lld", &n), solve();
return 0;
}
第9题 Luogu P1736 创意吃鱼法&P1387 最大正方形
Luogu P1736 创意吃鱼法
P1387 最大正方形
题意：见上。
解(最大正方形)：这题求一个最大的1正方形(对角线或全部)，设$dp(i,j)$为以$(i,j)$为右下顶点的最大1正方形边长，转移$dp(i,j)=min(dp(i-1,j-1), dp(i-1,j), dp(i,j-1))+1$, 并且$a(i,j)=1$。
创意吃鱼法这题与上面一题非常相似，只有预处理即可替换DP方程就能做出来了。
第10题 Bzoj 1057
第11题 Hdu 1024
Hdu 1024
题意：$m$子段和的最大值。
解：设$dp(j,i)$为分了$j$段，前$i$个数的最大值。(状态方便滚动数组)
那么转移$dp(j,i)=max(dp(j-1,k)|0 \leq k \leq i - 1)$
初始化$dp(0,0)=0, othewise=-INF$
求最大值时可以由上一层用数组存上一层的最大值，然后在这一层直接用。
知识点：用数组存上一层的最大值/最小值很好用，求 LCIS 也利用了类似的方法。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<limits.h>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define ULL unsigned long long
#define db double
const int MAXN = 1000000 + 5, INF = 2000000000;
int n, m, a[MAXN], dp[MAXN], whw[MAXN];
void clean() {
}
int solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), dp[i] = -INF;
dp[0] = 0;
for (int i = 0; i <= n; i++) {
whw[i] = std::max(dp[i], -INF);
if (i - 1 >= 0) whw[i] = std::max(whw[i], whw[i - 1]);
}
int ans = -INF;
for (int j = 1; j <= m; j++) {
// printf("j=%d\n", j);
for (int i = 1; i <= n; i++) {
dp[i] = std::max(whw[i - 1] + a[i], dp[i - 1] + a[i]);
//printf("i=%d, dp[i]=%d, whw[i - 1]=%d, dp[i - 1]=%d\n", i, dp[i], whw[i - 1], dp[i - 1]);
if (j == m) ans = std::max(ans, dp[i]);
}
dp[0] = -INF;
for (int i = 0; i <= n; i++) {
whw[i] = std::max(dp[i], -INF);
if (i - 1 >= 0) whw[i] = std::max(whw[i], whw[i - 1]);
}
}
printf("%d\n", ans);
return 0;
}
int main() {
while (scanf("%d%d", &m, &n) == 2) solve();
return 0;
}
第12题 Hdu 1069
Hdu 1069
题意：给出一些长方体，然后让你把他堆成塔，要求下面的塔的要比上面的塔大（长和宽），而且每一种长方体的数量都是无限的。
解：发现本题就是一个二维上升序列。我们对于每个长方形设 DP 状态。设$dp(i)$为以$i$长方形为顶的最高值。但是长方体的数量都是无限怎么办？我们发现长方形其实是有限的，最多选取 $ 6 $ 种。其中因为长宽可互换，只用存 $ 3 $ 种即可，在转移时讨论一下即可。转移就：
if (blk[i].mj < blk[j].mj && ((blk[i].x < blk[j].x && blk[i].y < blk[j].y) || (blk[i].x < blk[j].y && blk[i].y < blk[j].x))) dp[i] = max(dp[i], dp[j] + blk[i].z);
初始化所有dp[i] = blk[i].z
知识点：对于无穷，我们尝试化成有限。(复杂化简单)
序列上升问题与 DP 有关。
排序后 DP。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<limits.h>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define ULL unsigned long long
#define db double
const int MAXN = 35;
struct data {
int x, y, z, mj;
bool operator < (const data &b) const {return mj > b.mj;}
}blk[MAXN * 3];
int kase = 0, n, cnt, dp[MAXN * 3];
inline void ins(int a, int b, int c) {blk[++cnt] = (data){a, b, c, a * b};}
void clean() {
ms(dp, 0), cnt = 0;
}
int solve() {
clean();
for (int a, b, c, i = 1; i <= n; i++) scanf("%d%d%d", &a, &b, &c), ins(b, c, a), ins(a, c, b), ins(a, b, c);
std::sort(blk + 1, blk + 1 + 3 * n);
for (int i = 1; i <= 3 * n; i++) dp[i] = blk[i].z;
for (int i = 2; i <= 3 * n; i++)
for (int j = 1; j < i; j++) if (blk[i].mj < blk[j].mj && ((blk[i].x < blk[j].x && blk[i].y < blk[j].y) || (blk[i].x < blk[j].y && blk[i].y < blk[j].x))) dp[i] = std::max(dp[i], dp[j] + blk[i].z);
int ans = 0;
for (int i = 1; i <= 3 * n; i++) ans = std::max(dp[i], ans);
printf("Case %d: maximum height = %d\n", kase, ans);
return 0;
}
int main() {
while (scanf("%d", &n) == 1 && n) kase++, solve();
return 0;
}
第13题 Hdu 1074
Hdu 1074
题意：主人公有$n$门功课要做，每门功课做完需要一定的时间，而且每门功课有一个最后期限，如果该门功课延后一天交就得扣一分，而且每做一门功课主人公就一定把它做完为止，不会中途停下来再去做其他的。问怎样安排可使扣的分最少，如果有多组解，输出字典序最小的。
解：贪心是错的。本题数据范围小，并且是最优化问题，可以考虑状压。状压维护当前已经完成的功课。然后根据状态转移来更新答案。具体可以看代码注释。
知识点：
状压条件
1、数据范围小
2、原题是最优化/计数问题
3、顺序相对给出序列一般不单调/或者是维护集合
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<limits.h>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define ULL unsigned long long
#define db double
int n, dl[20], len[20];
char s[20][105];
std::stack<int > stk;
int dp[(1 << 20) + 5], dp_tm[(1 << 20) + 5], dp_lst[(1 << 20) + 5], dp_sub[(1 << 20) + 5];
//dp 是最优的扣分值， dp_tm 是在最优的扣分值下的用掉的时间，dp_lst 表示当前状态由哪个状态转移过来，dp_sub 表示当前状态是做了某门科目后得到的状态
void clean() {
}
int solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%s%d%d", s[i] + 1, &dl[i], &len[i]);
ms(dp, 67), dp[0] = 0, dp_tm[0] = dp_lst[0] = dp_sub[0] = 0;
for (int st = 1; st < (1 << n); st++) {
for (int i = n; i; i--) {
if ((1 << (i - 1)) & st) {
int nst = st - (1 << (i - 1));
int val = std::max(0, dp_tm[nst] + len[i] - dl[i]);//会扣的分
if (dp[nst] + val < dp[st]) {
dp[st] = dp[nst] + val;
dp_lst[st] = nst, dp_sub[st] = i, dp_tm[st] = dp_tm[nst] + len[i];
}
//if (st == 5 && i == 3) printf("nst=%d, dp[nst]=%d, val=%d, dp[st]=%d\n", nst, dp[nst], val, dp[st]);
}
}
}
//倒序输出
for (int st = (1 << n) - 1; st != 0; st = dp_lst[st]) stk.push(dp_sub[st]);
printf("%d\n", dp[(1 << n) - 1]);
while (!stk.empty()) printf("%s\n", s[stk.top()] + 1), stk.pop();
return 0;
}
int main() {
int T; scanf("%d", &T);
while (T--) scanf("%d", &n), solve();
return 0;
}
第14题 Luogu P2893 [USACO08FEB]修路Making the Grade
Luogu P2893 修路Making the Grade
题意：农夫约翰想改造一条路，原来的路的每一段海拔是$A_i$，修理后是$B_i$，花费$|A_i – B_i|$。我们要求修好的路是单调不升或者单调不降的。求最小花费。
解：设$dp(i,j)$为前$i$条路符合上升并且第$i$条路海拔为$j$的最优花费
然后$dp(i,j)=min(dp(i-1,k)+|j-A_i| | 1 \leq k \leq j)$
这样是$O(n^3)$的，然后发现$dp(i-1,k)$与$j$无关所以可以在上一层预处理一下变成$O(n^2)$
知识点：
1、一道题一时调试不出来可以放一下，然后之后来调估计就马上调出来了
2、用数组可以求出上一层的最值优化DP
3、花费有时候也可以表示在状态上
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const LL MAXN = 2000 + 5;
std::vector<LL > vec;
LL n, whw, a[MAXN], b[MAXN], dp[MAXN][MAXN], gg[MAXN];
inline LL abss(LL x) {return x > 0 ? x : -x;}
void clean() {
for (LL i = 0; i <= n; i++)
for (LL j = 0; j <= n; j++) dp[i][j] = LONG_LONG_MAX / 2;
for (LL i = 0; i <= n; i++) gg[i] = LONG_LONG_MAX / 2;
}
int solve() {
clean();
for (LL i = 1; i <= n; i++) scanf("%lld", &a[i]), vec.push_back(a[i]);
std::sort(vec.begin(), vec.end()), whw = std::unique(vec.begin(), vec.end()) - vec.begin();
for (LL i = 1; i <= n; i++) b[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
LL ans = LONG_LONG_MAX / 2;
dp[0][0] = 0;
for (LL j = 1; j <= whw; j++) gg[j] = 0;
for (LL i = 1; i <= n; i++) {
for (LL j = 1; j <= whw; j++) {
dp[i][j] = gg[j] + abss(vec[j - 1] - a[i]);
gg[j] = std::min(gg[j - 1], dp[i][j]);
if (i == n) ans = std::min(ans, dp[i][j]);
}
}
std::cout << ans;
return 0;
}
int main() {
scanf("%lld", &n), solve();
return 0;
}
第15题 Luogu P2340 奶牛会展
Luogu P2340 奶牛会展
题意：见上。
我先没想背包，想到一个状态是$dp(PrefixCows, IQ, EQ)=max(IQ+EQ)$，显然GG，而且很奇怪
发现这个状态记录$EQ$是无用的，所以可以$dp(PrefixCows, IQ)=max(EQ)$，然后转移发现就是在做背包，滚动数组优化空间，时间很紧张所以看命过不过吧。
第16题 Loj 10153 二叉苹果树
Loj 10153 二叉苹果树
题意：见上。
解：设$dp(u,i)$为$u$点子树中选了$i$条边的最大值，做个简单背包即可。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
namespace flyinthesky {
const int MAXN = 100 + 5;
struct edge {int u, v, w, nxt;} ed[MAXN * 2];
int n, q, en, hd[MAXN], dp[MAXN][MAXN];
void ins(int x, int y, int w) {ed[++en] = (edge){x, y, w, hd[x]}, hd[x] = en;}
int dfs(int u, int i, int fa) {
if (dp[u][i] >= 0) return dp[u][i];
int lc = -1, rc = -1;
int lv = 0, rv = 0;
for (int o = hd[u]; o > 0; o = ed[o].nxt) if (ed[o].v != fa) {
if (lc == -1) lc = ed[o].v, lv = ed[o].w; else if (rc == -1) rc = ed[o].v, rv = ed[o].w;
}
dp[u][i] = 0;
if (lc == -1 && rc == -1) return dp[u][i];
if (i - 1 >= 0) dp[u][i] = max(dp[u][i], dfs(lc, i - 1, u) + lv);
if (i - 1 >= 0) dp[u][i] = max(dp[u][i], dfs(rc, i - 1, u) + rv);
for (int j = 0; j <= i - 2; ++j) dp[u][i] = max(dp[u][i], dfs(lc, j, u) + dfs(rc, i - 2 - j, u) + lv + rv);
return dp[u][i];
}
void clean() {
en = 0, ms(hd, -1), ms(dp, -1);
}
int solve() {
scanf("%d%d", &n, &q);
clean();
for (int x, y, w, i = 1; i < n; ++i) scanf("%d%d%d", &x, &y, &w), ins(x, y, w), ins(y, x, w);
dfs(1, q, 0);
printf("%d\n", dp[1][q]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
第17题 51nod 1007 正整数分组
51nod 1007 正整数分组
题意：见上。
刚开始想贪心来着。好像行不通。
最优化问题，DP。
两种DP：
1、由于一组数肯定要逼近$\frac 12 sum$，所以用$\frac 12 sum$当容量跑背包即可
2、设$dp(i, x)$为前$i$个数差值为$x$是否存在。转移显然。
第18题 Hdu 5256 序列变换
Hdu 5256 序列变换
题意：求将一个序列改成严格单调的最小次数。
解：答案为序列$a_i-i$的不严格单调的最小次数，有一个对应的思想。
不严格单调的最小次数为$n-LIS$。
注意二分的 upper_bound
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
int kse = 0;
namespace flyinthesky {
int n, A[100000 + 5], b[100000 + 5], cnt;
void clean() {
cnt = 1;
for (int i = 0; i <= 100001; ++i) b[i] = -1000000000;
}
int solve() {
clean();
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &A[i]), A[i] -= i;
b[1] = A[1];
for (int i = 2; i <= n; ++i) {
if (A[i] >= b[cnt]) b[++cnt] = A[i];
else {
int pos = upper_bound(b + 1, b + 1 + cnt, A[i]) - b;
b[pos] = A[i];
}
}
printf("Case #%d:\n%d\n", ++kse, n - cnt);
return 0;
}
}
int main() {
int T; scanf("%d", &T);
while (T--) flyinthesky::solve();
return 0;
}
第19题 CodeForces E. Palindrome-less Arrays
发现等价于不存在三长度的回文串，奇偶分离后就是一个求相邻数不同的方案数。
对于整段$-1$求解即可。
容易写出一个$O(nk)$的DP，但是这里可以更简单。
设$dp(i,0/1)$表示当前有$i$个$-1$, 两边不等 / 等。
转移以后算就行。注意两边$-1$的特判
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MO = 998244353, MAXN = 200000 + 5;
LL ksm(LL a, LL b) {
LL ret = 1, bs = a;
while (b) {
if (b & 1) ret = (ret * bs) % MO;
bs = (bs * bs) % MO;
b >>= 1;
}
return ret;
}
LL n, k, a[MAXN], b[MAXN], tota, totb, dp[MAXN][2];
LL gg(LL *arr, LL n) {
LL l, r;
for (l = 1; l <= n && arr[l] == -1; ++l) ;
if (l == n + 1) return ksm(k - 1, n - 1) * k % MO;
for (r = n; r >= 1 && arr[r] == -1; --r) ;
LL ret = 1;
ret = ret * ksm(k - 1, l - 1) % MO;
ret = ret * ksm(k - 1, n - r) % MO;
LL lst = l;
for (LL i = l + 1; i <= r; ++i) {
if (arr[i] != -1) {
ret = (ret * dp[i - lst - 1][arr[i] == arr[lst]]) % MO;
lst = i;
}
}
return ret;
}
void clean() {
}
int solve() {
clean();
cin >> n >> k;
for (LL x, i = 1; i <= n; ++i) {
scanf("%lld", &x);
if (i % 2) a[++tota] = x; else b[++totb] = x;
}
dp[0][0] = 1, dp[0][1] = 0;
for (LL i = 1; i <= n; ++i) {
dp[i][0] = (dp[i - 1][0] * (k - 2) % MO + dp[i - 1][1]) % MO;
dp[i][1] = dp[i - 1][0] * (k - 1) % MO; // (k - 1) 下面
}
printf("%lld\n", (gg(a, tota) * gg(b, totb)) % MO);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
