首页 > 其他分享 >AT_dp 做题笔记

AT_dp 做题笔记

时间：2023-12-10 23:33:43浏览次数：32  
标签：std int long 笔记 using include dp

持续更新。

更好的阅读体验？

更朴素的阅读体验？

未完成题目

AT_dp_s, AT_dp_t, AT_dp_v, AT_dp_w, AT_dp_x, AT_dp_y, AT_dp_z。

AT_dp_a

Solution

青蛙只能从 \(i-1\) 或 \(i-2\) 跳过来，所以转移方程自然地就是 \(dp_i=min(dp_{i-1}+|h_i-h_{i-1}|,dp_{i-2}+|h_i-h_{i-2}|)\)。

Code

#include <bits/stdc++.h>
using namespace std;
long long h[int(1e5+10)],dp[int(1e5+10)];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>h[i];
	dp[2]=abs(h[2]-h[1]);
	for(int i=3;i<=n;i++) dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
	cout<<dp[n];
	return 0;
}

AT_dp_b

Solution

基本同上，不过转移方程涉及 \(k\) 个其余状态，稍加修改即可。

Code

#include <bits/stdc++.h>
using namespace std;
long long h[int(1e5+10)],dp[int(1e5+10)];
int main()
{
	memset(dp,0x3f,sizeof dp);
	int n,k;
	cin>>n>>k;
	dp[1]=0;
	for(int i=1;i<=n;i++) cin>>h[i];
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=k;j++)
		{
			if(i<=j) break;
			dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
		}
	}
	cout<<dp[n];
	return 0;
}

AT_dp_c

Solution

\(dp_{i,j}\) 表示第 \(i\) 天做第 \(j\) 件事的最大幸福度，从上一天的另外两件事转移过来。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long dp[int(1e5+10)][3],a[N],b[N],c[N];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];
	dp[1][0]=a[1];
	dp[1][1]=b[1];
	dp[1][2]=c[1];
	for(int i=2;i<=n;i++)
	{
		dp[i][0]+=a[i];
		dp[i][1]+=b[i];
		dp[i][2]+=c[i];
		dp[i][0]+=max(dp[i-1][1],dp[i-1][2]);
		dp[i][1]+=max(dp[i-1][0],dp[i-1][2]);
		dp[i][2]+=max(dp[i-1][0],dp[i-1][1]);
	}
	cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
	return 0;
}

AT_dp_d

Solution

01 背包板子，不必多讲。

Code

//2年前写的，码风巨丑
#include<bits/stdc++.h>
using namespace std;
long long M,N,w[205],c[205],f[100005];
int main(){
    cin>>N>>M;
    for(int i=1;i<=N;i++)cin>>w[i]>>c[i];
    for(int i=1;i<=N;i++){
        for(int j=M;j>=w[i];j--)f[j]=max(f[j],f[j-w[i]]+c[i]);
    }
    cout<<f[M];
    return 0;
}

AT_dp_e

Solution

与上一题不同，因为 \(W\) 巨大但是 \(w_i\) 很小，故考虑用价值作为状态，即 \(dp_i\) 表示达到价值 \(i\) 所需最小重量，转移方程就随便推也能推出来了。

Code

#include <bits/stdc++.h>
using namespace std;
long long dp[int(1e6+10)],w[110],v[110];
int main()
{
	long long n,m,sum=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
		sum+=v[i];
	}
	memset(dp,0x3f,sizeof dp);
	dp[0]=0;
	for(int i=1;i<=n;i++)
	for(int j=sum;j>=v[i];j--)
	dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
	for(int i=sum;i;i--) if(dp[i]<=m)
	{
		cout<<i;
		return 0;
	}
}

AT_dp_f

Solution

首先这是模板，但是要输出 LCS，那就标记每一次转移从哪一个状态转过来，输出的时候倒序输出 \(dp_{1,n}\) 的上一个状态的上一个状态的上一个状态……

Code

#include <bits/stdc++.h>
using namespace std;
string s,t;
int dp[3010][3010],type[3010][3010];
int main()
{
	cin>>s>>t;
	int n=s.size(),m=t.size();
	s=' '+s;
	t=' '+t;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		if(s[i]==t[j])
		{
			dp[i][j]=dp[i-1][j-1]+1;
			type[i][j]=1;
		}
		else
		{
			if(dp[i][j-1]>dp[i-1][j])
			{
				dp[i][j]=dp[i][j-1];
				type[i][j]=2;
			}
			else
			{
				dp[i][j]=dp[i-1][j];
				type[i][j]=3;
			}
		}
	}
	string ans;
	for(int i=n,j=m;i>0&&j>0;)
	{
		if(type[i][j]==1)
		{
			ans=s[i]+ans;
			i--;
			j--;
		}
		else if(type[i][j]==2) j--;
		else i--;
	}
	cout<<ans;
	return 0;
}

AT_dp_g

Solution

DAG 最长路板。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int> G[N];
int dp[N];
int dfs(int u)
{
	if(dp[u]) return dp[u];
	for(auto v:G[u]) dp[u]=max(dp[u],dfs(v)+1);
	return dp[u];
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
	}
	int ans=-1;
	for(int i=1;i<=n;i++) ans=max(ans,dfs(i));
	cout<<ans;
	return 0;
}

AT_dp_h

Solution

过河卒。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
string s[1010];
int dp[1010][1010];
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>s[i],s[i]=' '+s[i];
	dp[1][1]=1;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		if(s[i][j]=='#'||(i==1&&j==1)) continue;
		dp[i][j]=dp[i-1][j]+dp[i][j-1];
		dp[i][j]%=mod;
	}
	cout<<dp[n][m];
	return 0;
}

AT_dp_i

Solution

看一眼数据范围：\(N\) 特别小，想到二维状态，于是想到 \(dp_{i,j}\) 表示前 \(i\) 个硬币有 \(j\) 个向上的概率，\(dp_{i,j}\) 由 \(dp_{i-1,j-1}\) 或 \(dp_{i-1,j}\) 转移过来，剩下的很简单了。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=3010;
double dp[N][N],p[N];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>p[i];
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=i;j++)
		dp[i][j]+=dp[i-1][j]*(1.0-p[i])+dp[i-1][j-1]*p[i];
	}
	double ans=0;
	for(int i=(n+1)/2;i<=n;i++) ans+=dp[n][i];
	printf("%.10lf",ans);
	return 0;
}

AT_dp_j

Solution

先考虑最朴素的 dp，\(dp_{a,b,c,d}\) 表示还剩下 \(a\) 个 \(0\) 寿司盘子，\(b\) 个 \(1\) 寿司盘子，以此类推。转移方程：\(dp_{a,b,c,d}=\frac{n}{b+c+d}+\frac{b}{b+c+d}\times dp_{a+1,b-1,c,d}+\frac{c}{b+c+d}\times dp_{a,b+1,c-1,d}+\frac{d}{b+c+d}\times dp_{a,b,c+1,d-1}\)。

然后发现始终有 \(a+b+c+d=n\)，考虑压缩掉第一维，变成三维 dp，复杂度 \(O(n^3)\)，可以通过，具体转移方程见代码。

Code

#include <bits/stdc++.h>
using namespace std;
double dp[310][310][310];int cnt[4];
int main()
{
	double n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		cnt[x]++;
	}
	for(int k=0;k<=n;k++)
	for(int j=0;j<=n;j++)
	for(int i=0;i<=n;i++)
	{
		double x=i+j+k;
		if(!i&&!j&&!k) continue;
		if(i) dp[i][j][k]+=dp[i-1][j][k]*(i/(x));
		if(j) dp[i][j][k]+=dp[i+1][j-1][k]*(j/(x));
		if(k) dp[i][j][k]+=dp[i][j+1][k-1]*(k/(x));
		dp[i][j][k]+=n/(x);
	}
	printf("%.10lf",dp[cnt[1]][cnt[2]][cnt[3]]);
	return 0;
}

AT_dp_k

Solution

稍微接触过博弈论的都知道，要解决胜负问题，就要求必胜态与必败态，那么定义 \(sta_i\) 为石子数量只剩 \(i\) 时初始时的先手是否可以胜利。显然对于 \(i\in A\) 都有 \(sta_i=1\)，那么假如某个状态 \(j\) 只可以通过状态 \(sta_k=1\) 转移，且 \(|j-k|\in A\)，那么 \(j\) 就是必败态，否则是必胜态，所以 dp，启动！

Code

#include <bits/stdc++.h>
using namespace std;
int sta[int(1e5+10)],a[int(1e5+10)];
int main()
{
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=k;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i>=a[j]) sta[i]|=1-sta[i-a[j]];
		}
	}
	cout<<(sta[k]?"First":"Second");
	return 0;
}

AT_dp_l

Solution

设 \(dp_{l,r}\) 表示区间 \([l,r]\) 中最大的可以取到的 \(X-Y\)，那么自然分奇偶性讨论，如果 \(len=r-l+1\) 是偶数，先手取，否则后手取，然后推一下转移方程就行了。一定要先枚举 \(l\) 再枚举 \(len\) 然后再计算 \(r\)。

Code

#include <bits/stdc++.h>
using namespace std;
long long dp[3010][3010],a[3010];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int k=1;k<=n;k++)
	for(int i=1;i+k-1<=n;i++)
	{
		int j=i+k-1;
		if((n-k)%2) dp[i][j]=min(dp[i+1][j]-a[i],dp[i][j-1]-a[j]);
		else dp[i][j]=max(dp[i+1][j]+a[i],dp[i][j-1]+a[j]);
	}
	cout<<dp[1][n];
	return 0;
}

AT_dp_m

Solution

先考虑最暴力的 dp，\(dp_{i,j}\) 表示前 \(i-1\) 个小朋友共分走了 \(j\) 颗糖的方案数，易得 \(dp_{i,j}=\displaystyle\sum_{k=\max(0,j-a_{i-1})}^jdp_{i-1,k}\)，复杂度爆炸。

考虑优化它，由于涉及到和并且是静态的，想到前缀和优化 dp，于是有 \(sum_i=\displaystyle\sum_{j=0}^idp_{i-1,j}\)，转移方程就得以优化。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int dp[110][100010];
signed main()
{
	int n,k,sum=0;
	cin>>n>>k;
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		int a;
		cin>>a;
		sum=0;
		for(int j=0;j<=k;j++)
		{
			sum+=dp[i-1][j];
			if(j>a) sum-=dp[i-1][j-a-1];
			sum=(sum+mod)%mod;
			dp[i][j]=sum;
		}
	}
	cout<<dp[n][k];
	return 0;
}

AT_dp_n

Solution

石子合并。

Code

#include <bits/stdc++.h>
using namespace std;
long long a[410],dp[410][410],sum[410];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=n;i++)
	{
		memset(dp[i],0x3f,sizeof dp[i]);
		dp[i][i]=0;
	}
	for(int i=n;i;i--)
	for(int j=i+1;j<=n;j++)
	for(int k=1;k<j;k++)
	dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
	cout<<dp[1][n];
	return 0;
}

AT_dp_o

Solution

\(n\) 特别小，状压 dp。考虑集合 \(S\) 表示当前被选择过的男人，用二进制表示，由于题目要求的是一对一对，所以就有同样数量的 \(|S|\) 个女人，每次加入一个新的男人，考虑连能连的女人的方案数，最后叠加即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int dp[1<<22],g[22][22];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	cin>>g[i][j];
	dp[0]=1;
	for(int i=1;i<(1<<n);i++)
	{
		int sz=__builtin_popcount(i);
		for(int j=1;j<=n;j++)
		if(g[sz][j]&&(i>>j-1)&1)
		{
			dp[i]+=dp[i-(1<<j-1)];
			dp[i]%=mod;
		}
	}
	cout<<dp[(1<<n)-1];
	return 0;
}

AT_dp_p

Solution

跟没有上司的舞会很像，不同的是原题求最大快乐值，本题求方案数，所以转移应该是把所有儿子的 dp 值乘起来再取模。另外，dp 数组初值赋 \(1\)。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
const int mod=1e9+7;
vector<int> G[N];
int dp[N][2];
void dfs(int u,int fa)
{
	dp[u][0]=dp[u][1]=1;
	for(auto v:G[u])
	{
		if(v==fa) continue;
		dfs(v,u);
		dp[u][1]*=dp[v][0];
		dp[u][0]*=dp[v][1]+dp[v][0];
		dp[u][0]%=mod;
		dp[u][1]%=mod;
	}
}
signed main()
{
	int n;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0);
	cout<<(dp[1][0]+dp[1][1])%mod;
	return 0;
}

AT_dp_q

Solution

设 \(dp_i\) 表示前 \(i\) 朵花的最大价值，暴力的话有 \(dp_i=\max_{j=1}^{i-1}{dp_j(h_j<h_i)}+a_i\)，显然超时。

注意到 \(h_i\le n\)，考虑以 \(h_i\) 为下标开线段树，单点修改，区间求 \(\max\)，这些都是基本操作，然后就做完了。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int maxx[N<<2],dp[N],h[N],a[N];
void update(int s,int t,int k,int v,int p)
{
	if(s==t&&t==k)
	{
		maxx[p]=v;
		return;
	}
	int m=s+t>>1;
	if(k<=m) update(s,m,k,v,p*2);
	else update(m+1,t,k,v,p*2+1);
	maxx[p]=max(maxx[p*2],maxx[p*2+1]);
}
int query(int l,int r,int s,int t,int p)
{
	if(l<=s&&t<=r) return maxx[p];
	int m=s+t>>1,ans=-1;
	if(l<=m) ans=max(ans,query(l,r,s,m,p*2));
	if(r>m) ans=max(ans,query(l,r,m+1,t,p*2+1));
	return ans;
}
signed main()
{
	int n,ans=-1;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>h[i];
	for(int i=1;i<=n;i++) cin>>a[i],dp[i]=a[i];
	for(int i=1;i<=n;i++)
	{
		dp[i]=query(1,h[i],1,n,1)+a[i];
		ans=max(ans,dp[i]);
		update(1,n,h[i],dp[i],1);
	}
	cout<<ans;
	return 0;
}

AT_dp_r

Solution

这题是典吧。把初始时的矩阵求 \(K\) 次方再把矩阵里的数求和就行了。至于证明，传递闭包应该能证。

Code

#include <bits/stdc++.h>
using namespace std;
long long n,k;
const long long mod=1e9+7;
struct matrix
{
	long long g[101][101],sz;
};
matrix unit()
{
	matrix ret;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		if(i==j) ret.g[i][j]=1;
		else ret.g[i][j]=0;
	} 
	return ret;
}
matrix emp()
{
	matrix ret;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	ret.g[i][j]=0;
	return ret;
}
matrix times(matrix a,matrix b)
{
	matrix ans;
	ans=emp();
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	for(int l=1;l<=n;l++)
	ans.g[i][j]=(ans.g[i][j]+a.g[i][l]*b.g[l][j]%mod)%mod;
	return ans;
}
matrix mqpow(matrix b,long long p)
{
	matrix ret;
	ret=unit();
	while(p)
	{
		if(p&1) ret=times(ret,b);
		b=times(b,b);
		p>>=1ll;
	}
	return ret;
}
int main()
{
	cin>>n>>k;
	matrix a;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	cin>>a.g[i][j];
	matrix ans;
	long long ret=0;
	ans=mqpow(a,k);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		if(ans.g[i][j]) ret+=ans.g[i][j],ret%=mod;
	}
	cout<<ret;
	return 0;
}

AT_dp_u

Solution

类似 dp_o 的状压，设 \(i\) 为二进制下物品的集合，\(dp_i=\max{dp_j+dp_{i\oplus j}}\)，其中 \(j\) 为 \(i\) 的真子集（也是二进制），\(\oplus\) 为异或。

Code

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

标签：std,int,long,笔记,using,include,dp
From： https://www.cnblogs.com/Crazyouth/p/17893056.html

相关文章

  • Django笔记四十四之Nginx+uWSGI部署Django以及Nginx负载均衡操作
    本文首发于公众号：Hunter后端原文链接：Django笔记四十四之Nginx+uWSGI部署Django以及Nginx负载均衡操作这一篇笔记介绍如何使用Nginx+uWSGI来部署Django。上一篇笔记中有介绍直接使用uWSGI作为web服务器来部署Django，这一篇笔记介绍如何使用Nginx来部署。使用Ngin......
  • 程序员的思维修炼 读书笔记01
    Dreyfus模型将学习的过程分为五个不同的阶段或水平：1.新手（Novice）需要详细的指导——要手把手地教。新手不知道这些指导是否有效，或者哪些指导更加重要；因为没有上下文知识可供他们使用进行评估。因此，新手需要频繁迅速的成就感和有规律的反馈。一本好的入门指导书籍要提供有足够多的......
  • openGauss学习笔记-151 openGauss 数据库运维-备份与恢复-物理备份与恢复之gs_basebac
    openGauss学习笔记-151openGauss数据库运维-备份与恢复-物理备份与恢复之gs_basebackup151.1背景信息openGauss部署成功后，在数据库运行的过程中，会遇到各种问题及异常状态。openGauss提供了gs_basebackup工具做基础的物理备份。gs_basebackup的实现目标是对服务器数据库文件的......
  • B3637-DP【橙】
    这题我用sort的时候大意了，从1开始使用的下标但是用sort时没加1导致排序错误，排了半天错才发现。另外，这道题我似乎用了一种与网络上搜到了做法截然不同的自己的瞎想出来的做法，我的这个做法需要n^2级别的空间复杂度，但好在这道题数据刚刚好允许我开二维数组于是便AC了。随后开始看时......
  • C++学习笔记五：变量与数据类型（Auto类型）
    Auto允许编译器自己来推断变量的类型，这种新功能是在c++11引入的。这个关键字结合for循环使用可以节省变量类型的重复输入。VSCode可以在鼠标移动到变量上之后直接显示变量的类型。autovar1{12};//intautovar2{13.0};//doubleautovar3{14.0f};//floatautovar4{15......
  • Linux 笔记
    Whatdoes"{};"meaninthefindcommand?Ifyourun find with exec, {} expandstothefilenameofeachfileordirectoryfoundwith find (sothat ls inyourexamplegetseveryfoundfilenameasanargument-notethatitcalls ls orwhatevero......
  • Adaptive Graph Contrastive Learning for Recommendation论文阅读笔记
    Abstract在实际的场景中，用户的行为数据往往是有噪声的，并且表现出偏态分布。所以需要利用自监督学习来改善用户表示。我们提出了一种新的自适应图对比学习(AdaGCL)框架，该框架使用两个自适应对比视图生成器来进行数据增强，以更好地增强CF范式。具体的说，我们使用了两个可训练的视图生......
  • P1439-DP【绿】
    轻敌了啊...题目一共只有几句话但我却忽略了一个重大信息...总之我显示写出了时空复杂度都是n^2级别的朴素递推算法，这没什么，基本功而已，然后50分我试了试滚动数组，把空间复杂度降到了n级别，但没什么用，解决了MLE但仍然TLE。后来我想到记搜应该能算的更快，毕竟有些用不到的点用搜索就......
  • C++学习笔记四：变量与数据类型（布尔型）
    今天来整理一下布尔型变量的使用方法1.声明和初始化一个布尔类型的变量占据1Byte空间，数值0代表false，其他非0数值代表trueboolred_light{false};boolgreen_light{true};std::cout<<"sizeof(bool):"<<sizeof(bool)<<std::endl; 2.打印一个布尔变量std::......
  • wordpress整合 Prism.js实现代码高亮 切图网自用
    Prism.js是一个简约漂亮的代码高亮插件，就冲简单好用就值得一用，如何把它整合到wordpress，附代码，也是切图网自己再用的。代码添加到主题的functions.php中//自定义代码高亮按钮functionappthemes_add_quicktags(){if(wp_script_is('quicktags')){?><s......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99