JZTXT

AT_dp 做题笔记

发布时间 2023-12-10 23:31:30作者: Crazyouth

持续更新。

更好的阅读体验？

未完成题目

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;
}