20240124-动态规划期末考试

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-21 17:01:15

T417071 写作业

题目分析：
- 50% 的数据：dp或者dfs记忆化均可
$f[n]=min(f[n-1],f[n/2]+1$ ,$n$为偶数.

$f[n]=f[n-1]+1$ ,$n$为奇数.
- 100% 的数据，考察点：数学方法，二进制运算。参考代码：

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
ll n,cnt;
int main(){
	cin>>n;
	while(n>1){
		if(n&1)n--,cnt++;
		else n\/=2,cnt++;
	}
	cout<<cnt<<endl;
}

T417086 促销

题目分析贪心+01背包变形。购买商品的方式可以通过优惠，也可以单独购买。题目要求最少的购买件数，那么我们买便宜的件数会更多。因此先排序。设购买前i件的最少花费为$f[i]$. $$ f[i]=min(f[i-1]+a[i],f[i-k]+2 \times a[i])

参考代码

\/*
物品可以有用优惠购买，也可以不用优惠。 
*\/ 
#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+9;
ll a[N], f[N],n,p,k,ans=0;
int main() {
    cin >> n>>p>>k;
   	for(int i=1;i<=n;i++)cin>>a[i],f[i]=2e9;
   	sort(a+1,a+1+n);
   	for(int i=1;i<=n;i++){
   		if(f[i-1]>p) break;
   		f[i]=min(f[i],f[i-1]+a[i]);
   		if(i>=k)f[i]=min(f[i],f[i-k]+2*a[i]);
   		if(f[i]<=p)ans=i;
	}
	cout<<ans<<endl;
}

T418732 种花还是种草

题目大意给出有 $N $个顶点的带边权完全图，选任意条顶点不重合的线段，求最大边权和。 $N<=16$,暴搜或者状压DP都可以。

状态DP,设$f(i)$为选了二进制i中包含点的最大距离，从$i$状态中枚举其中的两个点$j,k$个点为新连接的两个点，则，则转移方程为 $$ f(i)=max(f(i-2^j-2^k)+a_{i,j})
$$

时间复杂度$o(n^22^n)$

参考代码

#include <bits\/stdc++.h>
using namespace std;
int a[1010][1010];
long long f[1010101];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n-1; ++i) for (int j = i + 1; j < n; ++j) cin >> a[i][j];
	for (int i = 0; i <= (1 << n); ++i) {
		for (int j = 0; j < n; ++j) {
			if (i & (1 << j)) {
				for (int k = j + 1; k < n; ++k) {
					if (i & (1 << k)) f[i] = max(f[i ^ (1 << j) ^ (1 << k)] + a[j][k], f[i]);
				}
			}
		}
	}
	long long an = 0;
	for (int i = 0; i <= (1 << n); ++i) {
		an = max(an, f[i]);
	}
	cout << an << '\n';
	return 0;
}

T275408 收菜

每个袋子只能装1种物品，用刚好能装的下的最下背包来装这个物品。

60%的数据

$n^2$处理把物品放入哪个袋子。

100%的数据

要找更快的匹配方法。

方法一处理价值大的物品，给物品找袋子

贪心先从价值大的开始装。找到能装上且浪费空间最少的袋子，用上他。可以用一个袋子的多重集，二分查找，用掉一个删掉一个。

方法二找出袋子能装入的最大价值物品，给袋子找物品。看袋子能装入那些，从可以装入的物品中选出价值最大的。

把袋子和物品都按照体积排序。

把袋子大小能容纳的物品放入价值优先的优先队列。从能装入的物品中选择价值最大的。

T417069 小容玩Arcaea

题目分析考虑 DP。

$f(i,j)$为掷了$i$次硬币，计数器示数为连续$j$次为正面的最大收益。如果 $j=0$，则说明上一次掷到的是反面，所以上一次计数器的示数可以是$0$到 $i$之间的任意整数。因为上一次为反面，所以没有奖励。所以此时 $f(i,j)=max (f(i-1,k)),0\leq k<j$的最大值。

如果 $j≥1$,则说明上一次掷到的是正面，所以上一次计数器的示数一定是$j-1$。因为上一次是正面，所以会有奖励,所以此时

$f(i,j)=max(f(i-1,j-1)+a_i+b_i)$

答案为$max( f(n,k))$ $(0≤k≤n) $的总和。

参考代码

\/\/ABC261D
#include<iostream>
#define int long long
using namespace std;

const int N = 5010;

int n, m, ans;
int a[N], b[N];
int f[N][N];

signed main()
{
	cin >> n >> m;
	for(int i=1; i<=n; i++)
	{
		cin >> a[i];
	}
	for(int i=1; i<=m; i++)
	{
		int x, y;
		cin >> x >> y;
		b[x] = y;
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=0; j<=i-1; j++)
		{
			f[i][0] = max(f[i][0], f[i-1][j]);
		}
		for(int j=1; j<=i; j++)
		{
			f[i][j] = max(f[i][j], f[i-1][j-1] + a[i] + b[j]);
		}
	}
	for(int i=1; i<=n; i++)
	{
		ans = max(ans, f[n][i]);
	}
	
	cout << ans;
	return 0;
}

T417054 菜园

题目分析

一个有 $n$个格子的长纸条，第 $ i$个格子颜色为 $a_i$，价值为$ b_i$，现在要任选 $ k$种颜色，使得所有颜色是较大编号的格子都在较小编号的后面，求最大价值。

按照题目的意思，想在要求同样的格子颜色是连续的，那么需要选的两种颜色要分布的左右区间不能相交。这样就转换为一段一段区间的选。考虑设计以颜色为主体的状态，在加上所选的颜色种类数，也就是序列的长度，设计两维状态。设 $f(i,k)$为选了颜色 $i$ 为结尾，选了 $k$ 种颜色的最小价值。

那么需要统计每种颜色左侧和右侧出现的位置。记 $l_i$表示颜色$ i$ 第一次出现的位置， $ r_i$表示颜色 $i $最后一次出现的位置。那么只有满足$ r_j<l_i$时才能选$i,j$两种颜色。

$f(i,k)=min(f(j,k-1)+b[i])$，$j<i,r_j<l_i$. 第$i$种颜色对应的格子都在第j种格子的右边,$j<i$保证了颜色编号的上升。

时间复杂度$o(n^2k)$，加了区间限制条件后跑不满。

参考代码：


#include<bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int N=509; 
ll n,m,ans=-1,a[N],b[N];
ll l[N],r[N],f[N][N];
int main(){
	memset(f,-1,sizeof(f));
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
	for(int i=1;i<=n;i++){
		if(!l[a[i]]) l[a[i]]=i;
		r[a[i]]=max(r[a[i]],(ll)i);
	}
	f[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<i;j++){
		    if(l[i]<=r[j])continue;
			for(int k=1;k<=m;k++){
				if(f[j][k-1]!=-1) f[i][k]=max(f[i][k],f[j][k-1]+b[i]);
			}
		}
	}
	for(int i=1;i<=n;i++) ans=max(ans,f[i][m]);
	printf("%lld\n",ans);
	return 0;
}

T275421 逛菜园

题目大意

给你一个矩阵，从最后一行开始走，到了每一行第一个到的点时只能向左或者向上走，否则就可以向左向右向上走，最终走到第一行结束，求经过所有格子的最小值。

坐标类型的动态规划。考虑设 $f(i,j)$表示从到 $i$ 行，第 $j $可以获得的最小代价。

那么如何转移呢？

显然，进入第 $ i$ 行时的列数一定是 $≥j$ 的，这样才能到达第 $j $列。

考虑从刚进到第 $ i$ 行的点 $ k$ 跑到 $ j $的路径上的点一定是要算代价的，而同时可以再往左跑一段后跑回来。

这样此题复杂度就成 $O(n^3 )$ 的了,会超时。

如何优化呢?可以发现从右下走到左上的过程中，可以向左多跑一段，跑到哪里为止呢？越小越好，大于$0$就停止了，转化为预处理一个以 $j$ 为终点的最小子段和$sum(i,j)$。

两种情况：

从$i+1$过来,到$j$列的左侧逛一圈。
从$j+1$过来，如果$j+1$已经往左逛一圈了，到$j$这里就没必要再逛了，实际就是$j+1$的子段和是否连接了j，条件就是$sum[i][j]>0$。

$$ f(i,j)= min(f(i+1,j)+sum(i,j),f(i,j+1)+max(sum(i,j),0)) $$

于是此题复杂度 $ O(n^2 )$。

写作业: B3636 文字工作(数据增加了，和原题不一样)

促销:忘记来源了，自己造的数据

收菜:P6538 [COCI2013-2014#1] LOPOV

小容玩Arcaea:ABC261D

种花还是种草:AT_abc318_d [ABC318D] Gener

单调不下降的菜园: P9688 Colo.

逛菜园：P6649 「SWTR-5」Grid

描述：虽然叫动态规划的期末考试，也不一定都是动态规划，还是根据题目时间情况分析。

难度：普及-到普及+

赛时答疑与赛后题解：题解奖励：

lxn 的博客

博客

T417071 写作业

T417086 促销

T418732 种花还是种草

T275408 收菜

60%的数据

100%的数据

T417069 小容玩Arcaea

T417054 菜园

T275421 逛菜园

评论

发表评论