DP日记01 刷点线性DP
int_Hello_world · · 个人记录
日期：2023.1.11-1.12
前言：
这几天一直刷DP题，记点笔记防止自己摸鱼。
记录一下这几天做的题吧。这一篇记录几道线性dp题
以后再补,咕。
洛谷P1651
传送门
本来我是讲这个题的，就把注释写得挺详细的，不过大家都会了，就没讲,写好的注释没人看也怪可惜的，就放这里了。
思路都在代码里了
代码:
/*
先理题意：
有n块积木，每个积木高度为h[i]，每块积木可以选也可以不选
用这些积木去搭两座高度相同的塔，使两座塔高度尽可能高
思路：
两座塔只有高低之分，高的为高塔，低的为低塔
有四种情况:
第一种：第i块积木不用，所以j不发生改变。
第二种：第i块积木放到高塔上,高塔还是高塔。
第三种：第i块积木放到低塔上时，低塔还是低塔
第四种：第i块积木放到低塔上时，低塔变成高塔
*/
#include<bits/stdc++.h>
using namespace std;
int n,m,h[51],dp[51][500001],sum;//h[i]表示第i块积木的高度
//dp[i][j]表示前i块积木，高塔和低塔的高度差为j时所能达到的最高高度
//转移时也会出现4种情况：
//第一种：当前两座塔都没有使用第i块积木，所以直接由上一个状态转移过来
//dp[i][j]=dp[i-1][j]
//第二种:高塔使用了第i块积木，并且在上一个状态中该塔仍然是高塔
//dp[i][j]=dp[i-1][j-h[i]]+h[i]
//第三种：低塔使用了第i块积木，并且在上一个状态中该塔仍然是低塔
//dp[i][j]=dp[i-1][j+h[i]]
//第四种: 现在的高塔使用了第i块积木，但在用第i块积木前，它是低塔
//dp[i][j]=dp[i-1][h[i]-j]+j
//dp[i][j]在上面四种情况里取max即为第i个状态的最优答案
signed main(){
cin>>n;
for (int i=1;i<=n;++i) {
cin>>h[i];
sum+=h[i];//算一下所有积木加起来有多高
}
m=(sum+1)/2;//因为是建两个相同高度的塔，所以最高就是所有积木高度之和的一半
//因为默认向下下去整，所以这里给sum+1防止意外
memset(dp,-0x3f,sizeof(dp));//最终结果取max，dp[0][0]为0,所以其余初始化为负数
dp[0][0]=0;
//初始化
for (int i=1;i<=n;++i) { //第i块积木
for (int j=0;j<=m;++j) { //高的塔与低塔高度之差为j时
dp[i][j]=max(dp[i][j],dp[i-1][j]);//第一种情况
if (h[i]<=j) dp[i][j]=max(dp[i][j],dp[i-1][j-h[i]]+h[i]); //第二种情况
//注意只有当这块积木的高度小于两者高度差时才能转移过来
dp[i][j]=max(dp[i][j],dp[i-1][j+h[i]]); //第三种情况
if(h[i]>=j) dp[i][j]=max(dp[i][j],dp[i-1][h[i]-j]+j); //第四种情况
//只有当这块积木的高度大于两者高度差时才能转移过来
}
}
if (dp[n][0]) {
cout<<dp[n][0];//输出
}
else { //没法搭建出两座相同的塔
putchar('-');
putchar('1');
}
return 0;
}洛谷P1489
传送门
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[10231131],sum[10231311],dp[201][102313];
signed main(){
cin>>n;
for (int i=1;i<=n;++i) {
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
dp[0][0]=1;
for (int i=1;i<=n;++i) {
for (int j=n/2;j>=1;--j) {
for (int k=0;k<=sum[i];++k) {
if (k>=a[i]&&dp[j-1][k-a[i]]==1) {
dp[j][k]=1;
}
}
}
}
for (int i=sum[n]/2;i>=0;--i) {
if (dp[n/2][i]==1) {
cout<<i<<" "<<sum[n]-i;
return 0;
}
}
return 0;
}CF545C
传送门
#include<bits/stdc++.h>
using namespace std;
int n,m,dp[102311][3];
struct node{
int x,h;
}e[1021311];
bool cmp(node a,node b) {
return a.x<b.x;
}
signed main(){
cin>>n;
for (int i=1;i<=n;++i) {
cin>>e[i].x>>e[i].h;
}
sort(e+1,e+1+n,cmp);
dp[1][0]=1;dp[1][1]=1;
if (e[2].x-e[1].x>e[1].h) dp[1][2]=1;
for (int i=2;i<=n;++i) {
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
if(e[i].x-e[i-1].x>e[i-1].h) dp[i][0]=max(dp[i][0],dp[i-1][2]);
if(e[i].x-e[i-1].x>e[i].h) dp[i][1]=max(dp[i-1][0],dp[i-1][1])+1;
if (e[i].x-e[i-1].x>e[i].h+e[i-1].h) dp[i][1]=max(dp[i][1],dp[i-1][2]+1);
dp[i][2]=max(dp[i-1][0],dp[i-1][1])+1;
if(e[i].x-e[i-1].x>e[i-1].h) dp[i][2]=max(dp[i][2],dp[i-1][2]+1);
}
cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
return 0;
}
洛谷P3399 丝绸之路
传送门
是个比较水的题
整理下题意：
有n+1个城市从0到n排成一条链，初始时位于第0座城市，要前往第n座城市
每天可以选择走或者不走,每天最多走一座城市
问到达第n座城市最少消耗多少疲惫值,消耗的疲惫值与城市和天数有关.
确定状态： 设 dp[i][j] 表示第j天到达第i座城市最少消耗多少疲惫值
状态转移:
当前状态可能从两种状态转移过来
1.昨天就在这座城市，昨天选择休息
2.昨天在上一座城市，昨天选择走
比较容易推出状态转移方程：
dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+d[i]c[i])
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,dp[1011][1021],d[1023131],c[10231313];
//dp数组表示第i座城市，在第j天到达，最少消耗的疲惫值
signed main(){
//输入：
cin>>n>>m;
for (int i=1;i<=n;++i) {
cin>>d[i];
}
for (int i=1;i<=m;++i) {
cin>>c[i];
}
//初始化：
memset(dp,0x3f,sizeof(dp)); //因为要取min，所以先赋成极大值
for (int i=0;i<=m;++i) {
dp[0][i]=0;
//第0座城市不需要耗费体力，因此不论第几天都是0
}
//状态转移：
for (int i=1;i<=n;++i) {
for (int j=i;j<=m;++j) {
//因为一天最多走一个城市，所以最早也要第i天才能到第i座城市，所以循环从j=i开始
dp[i][j]=min(dp[i][j-1],dp[i-1][j-1]+d[i]*c[j]);
}
}
cout<<dp[n][m];
return 0;
}洛谷P1564 膜拜
传送门
做这个题的时候看到题解提到前缀和就感觉不妙，想起了NOIP2022第一题的痛苦经历 实际做的时候也确实调了好久，看来前缀和掌握的还是有些生疏了
简要概括一下这个题:
给定一个长度为n，由1和2组成的数列。要求对这个数列划分区间。
每个区间只需要满足下列条件中的一个即可；
1.区间里全为1
2.区间里全为2
3.区间里1和2的个数之差不能超过m
求最少需要划分成几个区间才能使所有区间都满足上述条件
确立状态：
设dp[i]表示前i个人最少需要几个机房（前i个数最少划成几个区间）
状态转移：
用两个for循环,i从1循环到n，j从1循环到i
表示第i到j个人放到同一个机房里（i，j分别为区间的左右端点。）
判断是否合法后进行状态转移。
转移方程非常好求 dp[i]=min(dp[i],dp[j-1]+1);
但限制条件需要推一下（调了好久）
用前缀和sum数组表示前i个人里喜欢1的和喜欢2的人数之差，当sum[i]绝对值小于m时，或者sum[i]的绝对值等于i时，说明从1到i个人可以放到一个机房。再利用一下前缀和的性质，推出限制条件为：
if (abs(sum[i]-sum[j-1])<=m||abs(sum[i]-sum[j-1])==i-j+1) dp[i]=min(dp[i],dp[j-1]+1)
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,dp[1023122],a[102123],sum[1023311];
signed main(){
cin>>n>>m;
for (int i=1;i<=n;++i) {
cin>>a[i];
sum[i]=sum[i-1];
if (a[i]==1) sum[i]+=1;
else sum[i]+=-1;
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;dp[1]=1;
for (int i=1;i<=n;++i) {
for (int j=1;j<=i;++j) {
if (abs(sum[i]-sum[j-1])<=m||abs(sum[i]-sum[j-1])==i-j+1) {
dp[i]=min(dp[i],dp[j-1]+1);
}
}
}
cout<<dp[n];
return 0;
}