20240124-动态规划期末考试
wflengxuenong
·
·
个人记录
T417071 写作业
-
题目分析：
$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])
参考代码
```cpp
/*
物品可以有用优惠购买，也可以不用优惠。
*/
#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)$
参考代码
```cpp
#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) $的总和。
参考代码
```cpp
//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)$，加了区间限制条件后跑不满。
参考代码：
```cpp
#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
描述：
虽然叫动态规划的期末考试，也不一定都是动态规划，还是根据题目时间情况分析。
难度：普及-到普及+
赛时答疑与赛后题解：
[题解](https://www.luogu.com.cn/blog/wflengxuenong/)
奖励：