NORTHLINE
← All recordsRECORD / 047
ACM

暑期集训DP

题意: 有A，B两个字符串，求f(a,b)_{max} = x*LCS(a,b)-y*|a|-z*|b|，其中x,y,z是题目里给的常数，a,b是A,B在子串。

ACM21 min read
By AkejyoOriginal writing

DP

A. 代码查重

题意: 有AA，BB两个字符串，求f(a,b)max=x∗LCS(a,b)−y∗∣a∣−z∗∣b∣f(a,b)_{max} = x*LCS(a,b)-y*|a|-z*|b|，其中xx,yy,zz是题目里给的常数，aa,bb是AA,BB在子串。

分析：设dp(i,j)dp(i,j)为AA的前ii位，BB的前jj位的最大答案值。转移的时候，对于a[i]a[i]位和b[j]b[j]位，可以分为a[i]=b[j]a[i]=b[j]和a[i]≠b[j]a[i]\neq b[j]两种：

  • 若a[i]=b[j]a[i]=b[j]，dp(i,j)=max {dp(i−1,j)−y,dp(i,j−1)−z,dp(i−1,j−1)+x−y−z,x−y−z}dp(i,j)=max\,\{dp(i-1,j)-y, dp(i,j-1)-z, dp(i-1,j-1)+x-y-z, x-y-z\}，即aa串的长度加一或bb串的长度加一或a,ba,b串的长度都加一(LCS(a,b)+1)(LCS(a,b)+1)或丢弃前面的串∣a∣=∣b∣=1|a|=|b|=1；
  • 若a[i]≠b[j]a[i]\neq b[j]，dp(i,j)=max(dp(i−1,j)−y,dp(i,j−1)−z,−y−z)dp(i,j)=max(dp(i-1,j)-y,dp(i,j-1)-z,-y-z), 即a串长度加一或b串长度加一或丢弃前面的串∣a∣=∣b∣=1|a|=|b|=1

遍历ii，jj得到dp(n,m)dp(n,m)即为答案

for(int i =1;i<=n;i++)
	for (int j = 1; j <= m; j++) 
		if (A[i] != B[j])
			dp[i][j]=max(max(dp[i-1][j]-y,dp[i][j-1]-z),-y-z);
		else
			dp[i][j]=max(max(dp[i-1][j-1]+x-y-z,dp[i-1][j]-y),max(dp[i][j-1]-z,x-y-z));

int n, m;
char A[5010], B[5010];
ll x, y, z;
ll dp[5010][5010];
ll an;
void solve(){
	sii(n, m); siii(x, y, z);
	scanf("%s", A+1); scanf("%s", B+1);
	for(int i =1;i<=n;i++)
		for (int j = 1; j <= m; j++) {
			if (A[i] != B[j])
				dp[i][j] = max(max(dp[i - 1][j] - y, dp[i][j - 1] - z), -y - z), an = max(an, dp[i][j]);
			else
				dp[i][j] = max(max(dp[i - 1][j - 1] + x - y - z, dp[i - 1][j] - y), max(dp[i][j - 1] - z, x - y - z)), an = max(an, dp[i][j]);
		}
	printf("%lld", an);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

B. 下棋

题意:一个 n∗nn*n 的矩形网图，每个格子都有值且互不相同，Alice和Bob轮流将棋子放置在棋盘上并获得所放位置的分数。下棋规则：

  1. 除去第一次放置棋子，每一次放置的棋子必须保证和上一次放置的棋子的曼哈顿距离大于 m；
  2. 棋子可以重叠放置。

Alice先手，棋局进行220222^{2022}回合后结束，问Alice在哪些位置下第一步棋必胜。

分析:Alice先手下完后获得分数a(i,j)，Bob如果想赢就必须在可选范围内选一个大于a(i,j)的格子才有可能赢，然后我们只要判断Bob选的这个格子是否是一个先手必胜点，如果是，那么Alice就寄了，Alice不能下a(i,j)。

DP:首先将格子分数a(i,j)从大到小排序，顺序遍历a。因为为了判断一个点是不是必胜点要判断可选范围内有无比该点分数大的必胜点，那么从大到小去dp的话就不需考虑大小了，只需考虑是否有必胜点即可。

​ 设dp(i,j)是(i,j)先手必胜或必败，查询是否存在一个点必胜点(x,y)，满足abs(x-i)+abs(y-j)>m。找必胜点可以有一点小结论：对于棋盘的四个角，分别保存距离最远的必胜点坐标，那么距离(i,j)曼哈顿距离最远的必胜点一定是保存的四个点之一，所以每次只需判断四个点就行，(i,j)判断是必胜点时再更新棋盘四点的保存点。

void update(point a) {//更新棋盘四点的最近点
	int tem;
	for (int i = 0; i < 4; i++) 
		if ((tem = mhd(QiPanSiJiao[i], a)) < jud[i].w)
			jud[i].x = a.x, jud[i].y = a.y, jud[i].w = tem;
}

for (int i = 2; i <= cnt; i++) {
		flag = 1;
		for (int j = 0; j < 4; j++)//查棋盘四点保存的必胜点与(i,j)的距离是否可取
			if (mhd(jud[j], P[i]) > m)
				flag = 0;
		if (flag) {//该点是必胜点
			ans.push_back(P[i]);
			update(P[i]);//更新棋盘四点保存的点
		}
	}

int n, m;
int num[2010][2010];
int M, x, y, cnt, flag;
struct point { int x, y, w; };
point jud[4];//左上、右上、左下、右下
point jud_xy[4];
point P[4000010];
vector<point>ans;
bool cmp(point a, point b) { return a.w > b.w; }
bool cmp2(point a, point b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
int mhd(point a, point b) { return abs(a.x - b.x) + abs(a.y - b.y); }
void update(point a) {//更新四点的最近点
	int tem;
	for (int i = 0; i < 4; i++) 
		if ((tem = mhd(jud_xy[i], a)) < jud[i].w)
			jud[i].x = a.x, jud[i].y = a.y, jud[i].w = tem;
}
void solve() {
	sii(n,m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			si(num[i][j]), P[++cnt] = { i,j,num[i][j] };
	jud[0].w = jud[1].w = jud[2].w = jud[3].w = 5000;
	jud_xy[0] = { 1,1,0 }, jud_xy[1] = { 1,n,0 }, jud_xy[2] = { n,1,0 }, jud_xy[3] = { n,n,0 };
	sort(P + 1, P + cnt + 1, cmp);
	update(P[1]);
	ans.push_back(P[1]);
	for (int i = 2; i <= cnt; i++) {
		flag = 1;
		for (int j = 0; j < 4; j++)
			if (mhd(jud[j], P[i]) > m)
				flag = 0;
		if (flag) {//该点是必胜点
			ans.push_back(P[i]);
			update(P[i]);
		}
	}
	sort(ans.begin(), ans.end(), cmp2);
	int ttt = ans.size();
	printf("%d\n", ttt);
	for (int i = 0; i < ttt; i++)
		printf("%d %d\n", ans[i].x, ans[i].y);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

D. 交互问题

题意：环上均匀分布mm个点,初始有3个指针指向这些点，每次拨动某一个指针使其指向a[i]a[i]点，不能连续两次拨动同一个指针，求最小拨动总距离。（拨动距离为0也算拨动）

分析: 如果三个三个操作看的话，会发现第i+1i+1次操作和第i−1i-1次操作之间不会有“不能连续两次拨动同一个指针”的限制要求，处理起来会方便很多。且我们还可以得出一个结论：第aia_i操作后必有一个指针是指向aia_i的。

DP：设dp[i][j]dp[i][j]为处理完aia_i，三个指针分别指向aia_i（这是必然的）、ai−1a_{i-1}（不能连续拨动同一个所以会有指向ai−1a_{i-1}的）、jj。接着转移dpdp：

  • 第i+1i+1个位置，可以拨动ai−1a_{i-1}指针，即：dp[i+1][j]=min(dp[i][j]+dis[ai−1][ai+1],dp[i+1][j])dp[i+1][j]=min(dp[i][j]+dis[a_{i-1}][a_{i+1}],dp[i+1][j])
  • 也可以拨动指向j的指针，即：dp[i+1][ai−1]=min(dp[i][j]+dis[j][ai+1],dp[i+1][ai−1])dp[i+1][a_{i-1}]=min(dp[i][j]+dis[j][a_{i+1}],dp[i+1][a_{i-1}])
for (int i=2;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			dp[i+1][j]=min(dp[i][j]+DIS[a[i-1]][a[i+1]],dp[i + 1][j]);//指向a[i-1]的
			dp[i+1][a[i-1]]=min(dp[i][j]+DIS[j][a[i+1]],dp[i+1][a[i-1]]);//指向j的
		}
	}

#include <bits/stdc++.h>
template<typename T>
inline void read(T& x) { x = 0; char c = getchar(); while (!isdigit(c))c = getchar(); while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } }
#define si(a) read(a)
#define sii(a,b) read(a),read(b)
#define siii(a,b,c) read(a),read(b),read(c)
#define fl float
#define ll long long int
#define ull unsigned long long int
using namespace std;
int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); }
int jd(int a) { return a < 0 ? (a * -1) : a; }
//const ll MOD = 924844033;
const int N = 5e5 + 10;
int n, m;
int s1, s2, s3;
int a[3010];
int dp[3010][3010];
int dis(int a, int b) { return min(abs(a - b), min(abs(a - 1 + m - b), abs(b - 1 + m - a))+1); }
int DIS[5010][5010];
void solve() {
	sii(n,m);
	siii(s1, s2, s3);
	for (int i = 1; i <= n; i++)si(a[i]);
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= m; j++)
			DIS[i][j] = dis(i, j);
	memset(dp, 63, sizeof(dp));
	dp[2][s3] = min(DIS[s1][a[1]] + DIS[s2][a[2]], DIS[s2][a[1]] + DIS[s1][a[2]]);
	dp[2][s1] = min(DIS[s2][a[1]] + DIS[s3][a[2]], DIS[s3][a[1]] + DIS[s2][a[2]]);
	dp[2][s2] = min(DIS[s1][a[1]] + DIS[s3][a[2]], DIS[s3][a[1]] + DIS[s1][a[2]]);
	if (s1 == a[1]) dp[2][a[1]] = min(dp[2][a[1]],dp[2][s1]);
	if (s2 == a[1]) dp[2][a[1]] = min(dp[2][a[1]], dp[2][s2]);
	if (s3 == a[1])dp[2][a[1]] = min(dp[2][a[1]], dp[2][s3]);
	if (s1 == a[2])dp[2][a[2]] = min(dp[2][a[1]], dp[2][s1]);
	if (s2 == a[2])dp[2][a[1]] = min(dp[2][a[1]], dp[2][s2]);
	if (s3 == a[2])dp[2][a[1]] = min(dp[2][a[1]], dp[2][s3]);
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i + 1][j] = min(dp[i][j] + DIS[a[i-1]][a[i+1]], dp[i + 1][j]);//指向a[i-1]的拨向a[i+1]
			dp[i + 1][a[i - 1]] = min(dp[i][j] + DIS[j][a[i+1]], dp[i + 1][a[i - 1]]);//指向j的拨向a[i+1]
		}
	}
	int ans = 1e9;
	for (int i = 1; i <= m; i++)
		ans = min(ans, dp[n][i]);
	printf("%d", ans);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

G. 魔法少女2

题意: 添加对角线使一个n*m的矩阵变成刚体，求加对角线的方案数。

刚体

刚体的定义：如果该图无法只改变其中一部分的形状，而使得余下的部分的形状保持不变。比如：对于一个2*3的矩阵，没加对角线的时候可以随意变化形状（各边的长度都没变，线也没变弯）。

1653045719747

加对角线后：下面的几种图都是一种刚体

1653045737202

分析: 发现每加一个对角线，会确定一系列边的垂直/平行关系。 如：对于一个1*2的矩阵

1653045788242 可以随意变换 1653045816023

添加一条对角线后，其变换能力受到了部分约束，且红色边与蓝色边将永远保持垂直关系

1653045883724

对应到原矩阵即为第一列的横边与第一行的竖边保持垂直。

我们发现刚体其实就是所有的横边与竖边都垂直，我们已经连了一条对角线使得一行的竖边与一列的横边垂直，再连一条就能让所有横边都垂直竖边

1653045906226

我们已经知道了连一条对角线的效果是让某一行的竖边与某一列的横边互相垂直，那么就可以转化成二分图问题。二分图左边是行，右边是列，矩阵变为刚体的情况即为二分图联通的情况。

1653045943045

都是二分图联通情况

现在我们就把问题转化成了：

一个左边n个点，右边m个点的二分图，使其联通的连线方案数有多少

直接去算联通数：容易出现算重复的情况，所以采用算出所有的连线情况减去不连通的连线方案的方式

1653045993063

for(n = 0;n<=N;n++)
		for (m = 0; m <= M; m++) {//求左边n个点右边m个点的二分图的联通方案数量
			dp[n][m] = three_mi[n * m];//这是所有连接情况，后面穷举不连通的减去
			for (int i = 0; i <= n - 1; i++) {
				for (int j = 0; j <= m; j++)
					if (i != n - 1 || j != m) {//i和j不能同时取到最大值
						dp[n][m] -= (C[n - 1][i] * C[m][j] % MOD * three_mi[(n - i - 1) * (m - j)] % MOD * dp[i + 1][j]) % MOD;
						dp[n][m] %= MOD;
					}
			}
			dp[n][m] = (dp[n][m] + MOD) % MOD;
		}

int n, m;
int N, M;
ll C[110][110];//C(i,j)排列数
ll dp[110][110];
ll three_mi[11000];
void C_i_j() {//预处理C(i,j)
	for (int i = 0; i <= 105; i++) {
		C[i][0] = 1, C[i][i] = 1;
		for (int j = 1; j < i; j++)
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
	}
}
void three_x() {//预处理3^x
	three_mi[0] = 1;
	for (int i = 1; i <= 10100; i++) three_mi[i] = (three_mi[i - 1]) * 3 % MOD;
}
void solve() {
	sii(N, M);
	C_i_j(); three_x();
	for(n = 0;n<=N;n++)
		for (m = 0; m <= M; m++) {//求左边n个点右边m个点的二分图的联通方案数量（该题里每个点的情况有3种
			dp[n][m] = three_mi[n * m];//这是所有连接情况，后面穷举不连通的减去
			for (int i = 0; i <= n - 1; i++) {
				for (int j = 0; j <= m; j++)
					if (i != n - 1 || j != m) {//i和j不能同时取到最大值
						dp[n][m] -= (C[n - 1][i] * C[m][j] % MOD * three_mi[(n - i - 1) * (m - j)] % MOD * dp[i + 1][j]) % MOD;
						dp[n][m] %= MOD;
					}
			}
			dp[n][m] = (dp[n][m] + MOD) % MOD;//取余，不然会寄
		}
	printf("%lld", dp[N][M]);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

H. 矿物储量不足

题意：一颗有n个节点的树，每个节点的权值为1或-1，求树上以1~n节点为根的连通块的最大权值和

树上 DP

分析：其实该题是要求包含i节点的连通块的最大权值和，先以1为根节点，如果我们知道了i子树里包含i的连通块的最大权值和，那么包含i的连通块的最大权值和就可以通过其父亲和i自己转移得到。

假设包含i的连通块的最大权值和为ans[i]：

  • 先跑一遍dfs确定各a[i]:对于i节点的每个儿子j，ans[i]+=max{0,ans[j]}ans[i]+=max\{0,ans[j]\}，最后ans[i]加上自己的权值。此时每个ans[i]是i子树里包含i的连通块的最大权值和；

    for (auto v : e[u]) 
		if(!vis[v])
			ans[u] += max(0, dfs(v));
ans[u] += value[u];

  • 再跑一遍dfs，对于i节点的儿子每个儿子j：

    1. 若ans[j]<0ans[j]<0，说明j子树里包含j的连通块最大权值和是负的，这时候就可以看它父亲ans[i]是否是正的，如果是正的，说明父亲i没取到j及其一下的部分还是正的，那ans[j]就直接加ans[i]，否则ans[j]不变；

    2. 若ans[j]>0ans[j]>0，显然ans[j]就取max{ans[j],ans[i]}max\{ans[j],ans[i]\};

    for (auto v : e[u]) {
		if (!vis2[v]) {
			if (an[v] < 0)
				an[v] += max(0,an[u]);
			else
				an[v] = max(an[v],an[u]);
			dfs2(v);
		}
	}

这样两波dfs后，每个节点的答案就出来了。

int n, m;
vector <int> e[N];
int c[N], an[N];
int vis[N], vis2[N];
int dfs(int u) {
	if (vis[u])
		return 0;
	vis[u] = 1;
	an[u] = c[u];
	int tot = 0;
	for (auto v : e[u]) 
		if(!vis[v])
			tot += max(0, dfs(v));//选或不选
	an[u] += tot;
	return an[u];
}
void dfs2(int u) {
	if (vis2[u])
		return;
	vis2[u] = 1;
	for (auto v : e[u]) {
		if (!vis2[v]) {
			if (an[v] < 0)
				an[v] += max(0,an[u]);
			else
				an[v] = max(an[v],an[u]);
			dfs2(v);
		}
	}
}
void solve() {
	si(n);
	for (int i = 1; i <= n; i++) {
		int tem; si(tem);
		c[i] = tem ? 1 : -1;
	}
	for (int i = 1; i < n; i++) {
		int a, b; sii(a, b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs(1);
	dfs2(1);
	for (int i = 1; i <= n; i++)printf("%d ", an[i]);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}/*10 2
1 2 3 3 3 4 5 3 4 5*/

I. 故意找茬是吧

题意：给定一个数组，每次询问[l,r]区间里的最大f(i,j)f(i,j)，l<=i,j<=rl<=i,j<=r。其中f(i,j)f(i,j)的计算满足下面式子：

1653048263083

分析：经过一波手动模拟可以碰出发现一个规律：f[i][j]=f[i][j−1]∧f[i+1][j]f[i][j]=f[i][j-1]\land f[i+1][j]。其中当i=j时f[i][j]f[i][j]的值是确定的为a[i]，所以就是斜着一行一行去更新f数组，最后再用同样的方法去更新区间里的最大f[i][j]f[i][j]。

for (int i = 1; i < n; i++) 
		for (int j = 1; j <= n; j++) 
			dp[j][i+j] = dp[j][i + j - 1] ^ dp[j + 1][i + j];//斜着一行一行走
for (int i = 1; i < n; i++)
		for (int j = 1; j <= n; j++) 
			dp[j][i + j] = max(dp[j][i+j],max(dp[j][i + j - 1], dp[j + 1][i + j]));

int n, m;
ll dp[5010][5010];
ll a[5010];
void yuchuli() {
	for (int i = 1; i <= n; i++)
		dp[i][i] = a[i];
	for (int i = 1; i < n; i++) 
		for (int j = 1; j <= n; j++) 
			dp[j][i+j] = dp[j][i + j - 1] ^ dp[j + 1][i + j];
	for (int i = 1; i < n; i++)
		for (int j = 1; j <= n; j++) 
			dp[j][i + j] = max(dp[j][i+j],max(dp[j][i + j - 1], dp[j + 1][i + j]));
}
void solve() {
	si(n);
	for (int i = 1; i <= n; i++)si(a[i]);
	int q; si(q);
	yuchuli();
	while (q--) {
		int l, r; sii(l, r);
		printf("%lld\n", dp[l][r]);
	}
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}/*10 2
1 2 3 3 3 4 5 3 4 5*/

L. 强迫症患者

题意: 给定一个整数数组，每次操作可以改变其中的一个数为另一个整数，求使数组严格递增所需要的最少操作次数。

最长不降子序列

分析：假如改变数时可以改变为任意数（包括小数），那么这个题就是求最长上升序列。

最长上升序列的求法：开一个新数组b，每次添加a[i]到b数组时，当遇到a[i]<a[i−1]a[i]<a[i-1]，那么就用a[i]来替换b里第一个大于等于a[i]的b[j]，因为显然a[i]放到那个位置是最优的。

重新回到该题，该题多了限制条件：只能改变成整数。这个条件会导致如果直接按照最长上升序列去写的话，a[i]替换b[j]的步骤就会出现问题，因为i到j之间可能距离非常大，而a[i]和b[j]的差值又非常小，这时候去替换可能会使i到j之间的数被卡死了。

举一个例子：数组[1,2,4,3,5]，直接最长上升序列写得到的是[1,2,4,5]或[1,2,3,5]，但你会发现这显然是不合理的，无论是3还是4，都不能在只改变一个值的情况下使整个数组严格递增。因为在处理b数组时，本来那个3（或4）是可以变成一个小数插到前面去的，但实际上3只能变成整数。

那么a[i]去更新b数组时什么情况才是合理的呢？我们会发现只有满足a[i]−b[j]>=i−ja[i]-b[j]>=i-j时才能去替换，即要满足a[i]−i>=b[j]−ja[i]-i>=b[j]-j。所以这个问题就转换成了求a[i]−ia[i]-i的最长不降子序列。用upper_bound优化时间。

int n, m;
int w;
int len = 1;
int a[N], ins[N];//ins[i]是长度为i的最长子序列的最后一个元素
void solve() {
	sii(n, w);
	for (int i = 1; i <= n; i++) {
		int tem; si(tem);
		a[i] = tem - i;
	}
	ins[1] = a[1];
	for (int i = 2; i <= n; i++)
		if (ins[len] >= a[i]) {
			int tem = upper_bound(ins + 1, ins + len + 1, a[i]) - ins;
			ins[tem] = a[i];
			len = max(tem, len);
		}
		else if(a[i]>ins[len])
			ins[++len] = a[i];
	printf("%lld\n", (ll)(n - len) * (ll)w);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}/*10 2
1 2 3 3 3 4 5 3 4 5*/

M. 啥b二次元 3

题意：1到n的排列，求使每个位置都比其相邻位置都大或都小的排序方案数（摇摆/波浪)

分析：设dp[i][j]dp[i][j]为长度为i且第一位是峰值的方案数。我们可以发现一个规律，对于一个第一位为峰值的摇摆数组，用高度做比喻，这个数离地面越高，那它离顶就越近，所以将每个数xx都换成n−x+1n-x+1(nn是该数组长度)，这个数组就会转换成一个第一位为波谷的摇摆数组。这时候就可以考虑dp转移了，本来dp[i][j]dp[i][j]为所有长度为i−1i-1、第一个数为11到j−1j-1且为波谷的方案数的总和，经过上面的转化，就可以算得下面的式子：

​ dp[i][j]=dp[i][j−1]+dp[i−1][i−j]dp[i][j] = dp[i][j - 1] + dp[i - 1][i - j]

for (int i = 1; i <= n; i++)dp[1][i] = 1;//初始化
for (int i = 2; i <= n; i++)
	for (int j = 1; j <= n; j++)
		dp[i][j] = (dp[i][j - 1] + dp[i - 1][i - j]) % MOD;

int n, m;
ll MOD;
ll dp[5000][5000];
void solve(){
	sii(n, MOD);
	for (int i = 1; i <= n; i++)dp[1][i] = 1;
	for (int i = 2; i <= n; i++)
		for (int j = 1; j <= n; j++)
			dp[i][j] = (dp[i][j - 1] + dp[i - 1][i - j]) % MOD;
	printf("%lld", (2 * dp[n][n])%MOD);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

O. 宝可梦

题意：多重背包

多重背包

朴素做法：

  1. 硬塞，这类物品有多少个就在数组里塞多少个，然后做01背包(TLE)

  2. 枚举第ii个物品拿了多少个：

    设dp[i][j]dp[i][j]为拿来前i种物品，价值为j的答案

    有状态转移方程: dp[i][j]=max {dp[i−1][j−k∗c]+k∗v}(0<=k<=m)dp[i][j]=max\,\{dp[i-1][j-k*c]+k*v\}(0<=k<=m)

二分优化：

​ 对于任何一个正数xx，都可以用一系列二的幂来表示。比如15=20+21+22+715=2^0+2^1+2^2+7。且用拆出来的这几个数相加可以得到11到xx中的任意数：1=1;2=2;3=1+2;4=4;5=1+4;6=2+4;7=1+2+4;8=1+7;9=2+7;10=1+2+7;11=4+7......1=1;2=2;3=1+2;4=4;5=1+4;6=2+4;7=1+2+4;8=1+7;9=2+7;10=1+2+7;11=4+7......

所有我们对每个mim_i都这样处理后，然后跑01背包即可。

int n, m, W;
ll v[N], w[N], num[N];
ll dp[44444];
int cut;
void solve() {
	sii(n, W);
	for (int i = 1; i <= n; i++) {
		ll a, b, c; siii(a, b, c);
		ll tem = 1;
		while (tem <= c)//二进制拆分
			v[++cut] = a * tem, w[cut] = b * tem, c -= tem, tem <<= 1;
		v[++cut] = a * c, w[cut] = b * c;
	}
	for (int i = 1; i <= cut; i++)
		for (int j = W; j >= w[i]; j--)
			dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
	printf("%lld", dp[W]);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

R. 顶点游走

题意: nn个节点的树，每个节点ii有权值aia_i，从11号节点出发求和aia_i，当sum<0sum<0时sumsum会自动变为00，可以从树上任意节点结束。求summaxsum_{max}

树上 DP

分析: 我们可以这样考虑每个节点：从该节点以后会存在sumsum归零情况或不会。分别设为F[i][0]F[i][0]和F[i][1]F[i][1]

  • 若考虑sumsum不会归零，dfs里每一节点F[i][1]F[i][1]都加上max {0,F[j][1]}max\,\{0,F[j][1]\},(j取i儿子)；

    F[u][1] += max(F[v][1], 0LL);//F[u][1]初始为w[u]

  • 若考虑sumsum会归零，我们可以先将该点的值F[i][0]F[i][0]设为00，用00把后面一堆负数全部提前解决了再处理。

    F[u][0] += max(F[v][0], F[v][1]);//F[u][0]初始为0

最后ansans取max {F[1][0],F[1][1]}max\,\{F[1][0],F[1][1]\}

int n, m;
int flag;
int vis[N], vis2[N];
ll F[N][2], w[N];
vector<int>e[N];
void dfs(int u) {
	if (vis[u])
		return;
	vis[u] = 1;
	F[u][1] = w[u];
	for (auto v : e[u]) {
		if (!vis[v]) {
			dfs(v);
			F[u][1] += max(F[v][1], 0LL);//不会变成0，直接求和
			F[u][0] += max(F[v][0], F[v][1]);//假设后面会变成0，也就是会有一段负的，F[u][0]初始为0把所有负的干了
		}
	}
}
void solve() {
	si(n);
	for (int i = 1; i < n; i++) {
		int a; scanf("%d", &a);
		e[a].push_back(i + 1);
		e[i + 1].push_back(a);
	}
	for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
	dfs(1);
	printf("%lld", max(F[1][0],F[1][1]));
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

X. 惊魂工创1

题意: 给定一个数，边有边权，每次操作可以使一个边的边权加一，要求每个叶节点到根的最短距离相等，求最小操作次数

树上 DP

分析：如果我们知道了一个节点ii到其后面的叶节点的最远距离DEP[i]DEP[i]，那么ii到jj的边要修改的值就是DEP[i]−DEP[j]−w[i][j]DEP[i]-DEP[j]-w[i][j](jj取ii的所有儿子，w[i][j]w[i][j]为ii到jj的边权)，最总答案即为DEP[i]DEP[i]的求和。

int n, m;
int mod,id;
int vis[500010],vis2[500010];
ll DEP[500010];
ll an;
struct edge {
	int v;
	ll w;
};
vector<edge>e[500010];
ll bfs1(int u) {
	if (vis[u])
		return 0;
	vis[u] = 1;
	for (auto it : e[u]) 
		if (!vis[it.v])
			DEP[u] = max(DEP[u], bfs1(it.v)+it.w);
	return DEP[u];
}
void bfs2(int u) {
	if (vis2[u])
		return;
	vis2[u] = 1;
	for (auto it : e[u]) {
		if (!vis2[it.v]) {
			an += DEP[u] - it.w - DEP[it.v];
			bfs2(it.v);
		}
	}
}
void solve(){
	sii(n,id);
	for (int i = 1; i < n; i++) {
		int a, b; 
		ll  t; siii(a, b, t);
		e[a].push_back({ b, t});
		e[b].push_back({ a,t});
	}
	bfs1(id); 
	bfs2(id);
	printf("%lld", an);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}

Z. 砍编剧

题意: 01背包

01 背包

直接给出01背包的做法：

for (int i = 1; i <= n; i++)
		for (int j = m; j >= w[i]; j--)
			dp[j] = max(dp[j], dp[j - w[i]] + k[i]);

#include <bits/stdc++.h>
template<typename T>
inline void read(T& x) { x = 0; char c = getchar(); while (!isdigit(c))c = getchar(); while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } }
#define si(a) read(a)
#define sii(a,b) read(a),read(b)
#define siii(a,b,c) read(a),read(b),read(c)
#define fl float
#define ll long long int
#define ull unsigned long long int
using namespace std;
int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); }
int jd(int a) { return a < 0 ? (a * -1) : a; }
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;
int n, m;
int k[550], w[550];
int dp[55555];
void solve() {
	sii(n, m);
	for (int i = 1; i <= n; i++)si(k[i]);
	for (int i = 1; i <= n; i++)si(w[i]);
	for (int i = 1; i <= n; i++)
		for (int j = m; j >= w[i]; j--)
			dp[j] = max(dp[j], dp[j - w[i]] + k[i]);
	printf("%d", dp[m]);
}
int main() {
	int t;
	/*si(t);
	while (t--)*/
	solve();
	return 0;
}
End of record / 047
← All records
READ NEXT暑期集训图论