本文共 11889 字，大约阅读时间需要 39 分钟。

2021年2月17日—动态规划基础测试总结

T1：音量调节

题目描述

一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。
音量用一个整数描述。输入文件中给定整数$beginLevel$，代表吉他刚开始的音量，以及整数$maxLevel$，代表吉他的最大音量。音量不能小于$0$也不能大于$maxLevel$。输入文件中还给定了$n$个整数$c[1],c[2],\dots ,c[n]$，表示在第$i$首歌开始之前吉他手想要改变的音量是多少。
吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。

输入格式

第一行依次为三个整数：$n,beginLevel,maxLevel$。
第二行依次为n个整数：$c[1],c[2],\dots ,c[n]$。

输出格式

输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于$0$或者高于$maxLevel$，输出$-1$。

样例数据

输入样例1：
3 5 10
5 3 7
输出样例1：
10

输入样例2：
4 8 20
15 2 9 10
输出样例2：
-1

数据规模与约定

$1\le n\le 50,1\le c[i]\le maxLevel,1\le maxLevel\le 1000,0\le beginLevel\le maxLevel.$
时间限制：$1s$
空间限制：$256MB$

考试分数

60pts

思路

不会利用dp解决此题，就进行暴搜（TLE自动机），超时了四组数据
暴力进行dfs，当音量不符合条件，即小于0或大于maxLevel时就返回，当num=n时，将ans与此时的音量进行比较求最大值

code

#include<bits/stdc++.h>using namespace std;const int N=55;int n,beginLevel,maxLevel,c[N],ans=-1;void dfs(int num,int yl){   	if(yl<0||yl>maxLevel) return;	if(num>n)	{   		if(ans<yl) ans=yl;		return;	}	dfs(num+1,yl+c[num+1]);	dfs(num+1,yl-c[num+1]);}int main(){   	cin>>n>>beginLevel>>maxLevel;	for(int i=1;i<=n;i++) scanf("%d",&c[i]);	dfs(0,beginLevel); 	cout<<ans;	return 0;}

正解 $O(n\times maxLevel)$

dp基础测试当然要用dp来写啦！(虽然考前没人告诉我这是dp测试(就算告诉了我也不会)）
bool $f_{i,j}$ 表示第 i 次调节音量是否能到达音量 j
初始化：第0次调节音量，音量肯定就是beginLevel啦，所以$f_{0,beginlevel}$=1
边界：音量 j 不能超过maxLevel，也不能低于0
状态转移： $if(f_{i-1,j+c[i]})f_{i,j}=1if(f_{i-1,j+c[i]})f_{i,j}=1$
最后从maxLevel到1遍历，第一个被标记的点即为所求结果，如果遍历后没有标记的点，输出-1即可

code

#include<bits/stdc++.h>using namespace std;const int N=55,M=1050;int c[N];bool f[N][M];int main(){   	freopen("ChangingSounds.in","r",stdin);	freopen("ChangingSounds.out","w",stdout);	int n,maxLevel,beginLevel;	cin>>n>>beginLevel>>maxLevel;	for(int i=1;i<=n;i++) cin>>c[i];	f[0][beginLevel]=1;	for(int i=1;i<=n;i++)		for(int j=0;j<=maxLevel;j++)		{   			if(j-c[i]>=0)				if(f[i-1][j-c[i]]==1) 					f[i][j]=1;			if(j+c[i]<=maxLevel)				if(f[i-1][j+c[i]]==1) 					f[i][j]=1;		}	for(int j=maxLevel;j>=0;j--)		if(f[n][j])		{   			cout<<j;			return 0;		}	cout<<-1;	return 0;}

T2 配对

题目描述

有 $N$ 个编号 $1,2,\cdots ,N$ 的男人和有 $N$ 个编号 $1,2,\cdots ,N$ 的女人。
对于每个$i,j(1\le i,j\le N)$ ，男人 $i$ 和女人 $j$ 的匹配度是一个整数 $a[i][j]$ 。当 $a[i][j]$=1时，男人$i$ 和女人 $j$ 可以匹配。当 $a[i][j]=0$ 时，两人不匹配。
芋头正在尝试配出N对一男一女的配对。 其中，每个男人和每个女人都必须且只能属于某一个配对。
请计算出芋头配出N对的方案数对 $10^9+7$取模的结果。

输入格式

第一行一个数字 $N$ 。
接下来 $N$ 行, 第$i$行有$N$ 个空格隔开的数 $a[i][1]$ 到 $a[i][n]$。
$N$
$a[1][1]\cdots \cdots a[1][N]$
$⋮$
$a[N][1]\cdots \cdots a[N][N]$

输出格式

输出芋头配出N对的方案数对 $10^9+7$ 取模的结果。

样例数据

输入样例1：
3
0 1 1
1 0 1
1 1 1
输出样例1：
3
样例解释1：
有三种配对的方法如下（ $(i,j)$ 表示男人 $i$与女人 $j$ 配对）：
$(1,2),(2,1),(3,3)$
$(1,2),(2,3),(3,1)$
$(1,3),(2,1),(3,2)$

输入样例2：
4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
输出样例2：
1
样例解释2：
有一种配对的方法如下：
$(1,2),(2,4),(3,1),(4,3)$

输入样例3：
1
0
输出样例3：
0

输入样例4：
21
0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1
1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0
0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1
0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0
1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1
0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0
0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1
0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1
0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1
0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0
0 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1
0 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1
1 1 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1
0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1
1 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1
0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1
0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0
1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0
1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0
输出样例4：
102515160

数据范围与提示

所有输入的值都是整数。
$1\le N\le 21$
$a[i][j]$ 是 $0$ 或 $1$ 。

考试分数

20pts

思路

f数组中表示状态的一维只开到了N的范围，导致运行时错误
更正以后为30pts，状态压缩运用不熟练导致循环次数过多，出现超时
由于n的范围很小，且a数组中只存在0和1，很容易想到使用状态压缩来解决本题。
从上到下遍历a数组，如果当前位置a[ i ][ j ]=1,则这个位置有价值，再用k循环表示第1…i-1行的状态，f[ i ][ j ]用来表示i行的数字能否表示k，如果可以则标记为1。如果当前这一位是1，且k所表示状态的第n-j位未被标记，就将第这一位和k所组成的数标记，直到扫到第n行，当前能够表示出各个数位都为1的状态，计数器sum加1。

code

#include<bits/stdc++.h>using namespace std;const int N=22;bool a[N][N],f[N][1<<N];int main(){   	int n,sum=0;	cin>>n;	for(int i=1;i<=n;i++)		for(int j=1;j<=n;j++)			scanf("%d",&a[i][j]);	for(int i=1;i<=n;i++) 		if(a[1][i]==1)			f[1][(1<<(n-i))]=1;	for(int i=1;i<=n;i++)	{   		for(int j=1;j<=n;j++)					for(int k=0;k<(1<<n);k++)				if(a[i][j]==1&&((k>>(n-j))&1)==0&&f[i-1][k]==1)				{   					f[i][k|(1<<(n-j))]=1;					if(i==n)						if(k|(1<<(n-j))==(1<<n)-1)							sum++;				}		for(int j=1;j<i;j++)			for(int k=0;k<(1<<n);k++)				if(f[i][k]) f[j][k]=1;	}	cout<<sum;	return 0;}

正解 $O(n^2\times 2^n)$

上述代码的问题比较大：1.没剪枝导致超时. 2.看错题，求的是方案数，我求的是能组成的对数. 3.没有对最后的结果取模
但微改以后其实就可以了，大体的思路是正确的

#include<bits/stdc++.h>using namespace std;const int N=22,mod=1e9+7;bool a[N][N];int f[N][1<<N];int main(){   	int n,sum=0;	cin>>n;	for(int i=1;i<=n;i++)		for(int j=1;j<=n;j++)			scanf("%d",&a[i][j]);	for(int i=1;i<=n;i++) 		if(a[1][i]==1)			f[1][(1<<(n-i))]=1;//初始化第一行	for(int i=2;i<=n;i++)//从第二行开始循环	{   		for(int k=0;k<(1<<n);k++)			if(f[i-1][k])//剪枝				for(int j=1;j<=n;j++)								if(a[i][j]==1&&((k>>(n-j))&1)==0)					{   						f[i][k|(1<<(n-j))]+=f[i-1][k];						f[i][k|(1<<(n-j))]%=mod;//取模					}	}			cout<<f[n][(1<<n)-1];	return 0;}

T3 补兵

题目描述

对于一个DOTA玩家，补兵个数（Creep Score）是衡量一名选手能力的重要指标，特别是打路人局的时候，补兵能力就更加关键了，因为常常会有队友和你抢补刀，比如，队友操控的老鹿在开大收兵，如果你操控的是幽鬼，就需要在老鹿的AOE中偷偷补上几刀来保证自己的发育。
我们自己建立一个模型来大致模拟以下情况：
现在有$n$个小兵，每个小兵有自己的血量$A[i]$(血量一定是正整数），你和老鹿轮流对小兵进行攻击。每次，你可以选择对某个小兵造成$1$点伤害（或者你可以选择不作为），接着，老鹿会对所有小兵造成$1$点AOE伤害，如此往复，直到所有小兵都死亡（血量变成$0$）。如果你对某个小兵造成致命伤害（使他的血量从$1$变成$0$）.那么你就补刀成功了！
对于给定的情形，你需要计算你最多可以补刀多少的小兵。

输入格式

本题有多组测试数据，第一行为一个整数$T$，表示测试组数。
对于每一组数据，第一行一个整数$N$，表示小兵的个数，随后第二行$N$个正整数，表示每个小兵的血量。

输出格式

对于每一组数据，输出一个整数$M$，表示补兵的最大数量。

数据规模

对于$30$%的数据，$N\le 100。$
对于$50$%的数据，$N\le 500，T\le 30，Ai\le 500。$
对于$100$%的数据，$1\le N\le 500，1\le T\le 70，1\le Ai\le 1000。$

样例数据

输入样例：
1
5
5 5 5 5 5
输出样例：
2

资源与时间限制

内存：$256MB$
时间：$1s$

考试分数

0pts

思路

无

T4 蜘蛛棋盘

题目描述

在一个$n\times m$ 的棋盘上，第一天每一个格子上都有一个蜘蛛。
在第一天里每一只蜘蛛都可以 向上 或 向下 或 向左 或 向右 爬行 一格（不能走出棋盘）； 或者待在原地不动。 多只蜘蛛可以爬行到同一个格子中。
通过第一天爬行后，第二天棋盘上出现了一些空的（没有蜘蛛的）格子。问，第二天棋盘上最多可以空出多少个格子？

输入格式

一行，两个正整数$n,m$。

输出格式

一行，一个非负整数，表示最多能空出的格子数

样例：

输入样例1：
1 1
输出样例1：
0

输入样例2：
2 3
输出样例2：
4

数据范围与提示

对于 $20$% 的数据，$n=1$ 。
对于 $50$% 的数据，$n\le 3$ 。
对于 $100$%的数据，$1\le n,m\le 40,1\le n\cdot m\le 40$。

考试分数

30pts

思路

没有想出来dp的正解，就奔着50分的数据一个一个手推打表，但依然推错了两组

code

#include<bits/stdc++.h>using namespace std;int main(){   	int n,m;	cin>>n>>m;	if(n==1)	{   		cout<<m*2/3;		return 0;	}	else if(n==2)	{   		if(m%2==1) cout<<(3*m-1)/2;		if(m%2==0) cout<<(3*m-2)/2;	} 	else if(n==3)//推错	{   		if(m==1) cout<<2;		if(m==2) cout<<4;		if(m==3) cout<<6;		if(m==4) cout<<8;		if(m==5) cout<<10;		if(m==6) cout<<12;		if(m==7) cout<<15;		if(m==8) cout<<17;		if(m==9) cout<<19;		if(m==10) cout<<21;		if(m==11) cout<<24;		if(m==12) cout<<26;		if(m==13) cout<<28;		}	else cout<<m*5/2;	return 0;}

T5 奶牛大聚会

题目描述

Bessie 正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。
每个奶牛居住在 $N$个农场中的一个，这些农场由 $N-1$ 条道路连接，并且从任意一个农场都能够到达另外一个农场。道路 $i$ 连接农场 $A_i$ 和 $B_i$，长度为 $L_i$。集会可以在 $N$ 个农场中的任意一个举行。另外，每个牛棚中居住着 $C_i$ 只奶牛。
在选择集会的地点的时候，Bessie 希望最大化方便的程度（也就是最小化不方便程度）。比如选择第 $X$ 个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参加集会所走的路程之和（比如，农场 $i$ 到达农场 $X$ 的距离是 $20$，那么总路程就是 $C_i\times 20$）。帮助 Bessie 找出最方便的地点来举行大集会。

输入格式

第一行一个整数 $N$ 。
第二到 $N+1$ 行：第 $i+1$ 行有一个整数 $C_i$。
第 $N+2$ 行到 $2N$ 行：第 $i+N+1$ 行为 $3$ 个整数：$A_i,B_i$ 和 $L_i$

输出格式

一行一个整数，表示最小的不方便值。

样例数据

输入样例：
5
1
1
0
0
2
1 3 1
2 3 2
3 4 3
4 5 3
输出样例：
15

数据范围与提示

$1\le N\le 105，1\le A_i\le B_i\le N，0\le C_i,L_i\le 10^3$

考试分数

50pts

思路

一道树形dp，类似于以前做过的（几乎一模一样）
错误原因在于没有开long long，导致5组大数据爆掉
改为long long后就A了
先利用邻接表（链式前向星）存图，siz[ i ]表示第i个点距离1号点的距离，sum1[ i ]表示去到1号点时要经过i号节点的人数，先用一遍dfs推出siz与sum数组，再用第二遍dfs推出状态转移方程dp[y]=dp[x]-(sum1[y]*edge[i].val)+((sum-sum1[y])*edge[i].val);
父亲节点dp[x]减掉到达他自身所花费的路程，再加上其他节点到达节点y所花费的路程。
最后比较每个节点的最小值

#include<bits/stdc++.h>using namespace std;const int N=1e5+10;int n,c[N];struct Star{   	int to,nxt,val;}edge[2*N];int head[N],tot=0,dp[N],siz[N],sum,sum1[N],ans=1e9;void Lian(int x,int y,int z){   	tot++;	edge[tot].to=y;	edge[tot].nxt=head[x];	edge[tot].val=z;	head[x]=tot;}void dfs1(int x,int father){   	sum1[x]=c[x];	for(int i=head[x];i;i=edge[i].nxt)	{   		int y=edge[i].to;		if(y==father) continue;		siz[y]=siz[x]+edge[i].val;		dfs1(y,x);		sum1[x]+=sum1[y];		}}void dfs2(int x,int father){   	for(int i=head[x];i;i=edge[i].nxt)	{   		int y=edge[i].to;		if(y==father) continue;		dp[y]=dp[x]-(sum1[y]*edge[i].val)+((sum-sum1[y])*edge[i].val);		dfs2(y,x);	}}int main(){   	freopen("gather.in","r",stdin);	freopen("gather.out","w",stdout);	cin>>n;	for(int i=1;i<=n;i++)	{   		scanf("%d",&c[i]);		sum+=c[i];	}	for(int i=1;i<n;i++)	{   		int a,b,l;		scanf("%d%d%d",&a,&b,&l);		Lian(a,b,l);		Lian(b,a,l);	}	siz[1]=0;	dfs1(1,0);	for(int i=1;i<=n;i++) dp[1]+=c[i]*siz[i];	dfs2(1,0);	for(int i=1;i<=n;i++) ans=min(dp[i],ans);	printf("%d",ans);	return 0;}

正解 $O(不会算）$

思路如上，改为long long即可

#include<bits/stdc++.h>using namespace std;const long long N=1e5+10;long long n,c[N];struct Star{   	long long to,nxt,val;}edge[2*N];long long head[N],tot=0,dp[N],siz[N],sum,sum1[N],ans=1e18;void Lian(long long x,long long y,long long z){   	tot++;	edge[tot].to=y;	edge[tot].nxt=head[x];	edge[tot].val=z;	head[x]=tot;}void dfs1(long long x,long long father){   	sum1[x]=c[x];	for(long long i=head[x];i;i=edge[i].nxt)	{   		long long y=edge[i].to;		if(y==father) continue;		siz[y]=siz[x]+edge[i].val;		dfs1(y,x);		sum1[x]+=sum1[y];		}}void dfs2(long long x,long long father){   	for(long long i=head[x];i;i=edge[i].nxt)	{   		long long y=edge[i].to;		if(y==father) continue;		dp[y]=dp[x]-(sum1[y]*edge[i].val)+((sum-sum1[y])*edge[i].val);		dfs2(y,x);	}}int main(){   	freopen("gather.in","r",stdin);	freopen("gather.out","w",stdout);	cin>>n;	for(long long i=1;i<=n;i++)	{   		scanf("%lld",&c[i]);		sum+=c[i];	}	for(long long i=1;i<n;i++)	{   		long long a,b,l;		scanf("%lld%lld%lld",&a,&b,&l);		Lian(a,b,l);		Lian(b,a,l);	}	siz[1]=0;	dfs1(1,0);	for(long long i=1;i<=n;i++) dp[1]+=c[i]*siz[i];	dfs2(1,0);	for(long long i=1;i<=n;i++) ans=min(dp[i],ans);	printf("%lld",ans);	return 0;}

当然不需要每个都开long long(我只是省事)，不过如果只将dp数组开为long long的话依然会被在中间计算的过程中爆掉