DP题训练

第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]公交车路线

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

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;
}

------ 本文结束 ------