DP题集

2018-08-21

字数统计: 1.7k字 | 阅读时长: 9min

1.noip2015 子串

#include<bits/stdc++.h>
using namespace std;
int f[2][201][201],s[2][201][201];//设s[ i ][ j ][ k ]为A用到了 i ，B用到了 j ，已经用了 k 个子串， 并且一定用了当前字符(A[i])时的方案数。
//设f[ i ][ j ][ k ]为A用到了 i ，B用到了 j ，已经用了 k 个子串， 无论用不用当前字符(A[i])时的方案数总和。
int n,m,k,now=1,last=0;
const int mod=1000000007;
char sa[1001],sb[201];
int main()
{
	scanf("%d %d %d",&n,&m,&k);
	scanf("%s",sa+1);
	scanf("%s",sb+1);
	f[0][0][0]=1;
	for(int i=1;i<=n;i++)
	{
		f[now][0][0]=1;
		for(int j=1;j<=m;j++)
		for(int v=1;v<=k;v++)
		{
			if(sa[i]==sb[j])
			{
				s[now][j][v]=(s[last][j-1][v]+f[last][j-1][v-1])%mod;
			}
			else
			{
				s[now][j][v]=0;
			}
			f[now][j][v]=(s[now][j][v]+f[last][j][v])%mod;
		}swap(now,last);	
	}
	printf("%d",f[last][m][k]);
	return 0;
}
/*
[i][j-1][k-1]+=f[i-1][j-1][k-1]
f[i][j][k]+=f[i-1][j-1][k]+f[l][j-1][k-1]
*/

2.LCS

#include<bits/stdc++.h>
using namespace std;
int f[5000][5000];
int n,a[10000],b[10000];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;
	else f[i][j]=max(f[i-1][j],f[i][j-1]);
	printf("%d",f[n][n]);
	return 0;
}

3.伪最长公共子序列

这道题看似为lcs,实则不然，看着数据范围，lcs妥妥的RE。所以要想其他方法。
（摘自其他博客）“我们可以以第一个串为标准，用第二个串来匹配第一个串，看能匹配多少，所以，其实第一个串的每个数字其实影响不大，只有知道它对应了第二串的哪个数字就好了，那么我们为什么不把他给的串重新定义一下？”

“比如他的样例：3 2 1 4 5 我们把他变成 1 2 3 4 5 用一个数组记录一下每个数字变成了什么，相当于离散化了一下3-1；2-2；1-3；4-4；5-5；”

“现在我们的第二串1 2 3 4 5 按我们离散化的表示：3 2 1 4 5”

“可能有些人已经懂了，我们把第一个串离散化后的数组是满足上升，反过来，满足上升的也就是满足原串的排列顺序的，（如果你不懂的话可以多看几遍这个例子）O(∩_∩)O~”

“好了 ，现在的问题就变成了求一个最长不下降序列！好了！解决完成！”

#include<bits/stdc++.h>
using namespace std;
int n,a[101000],b[101000],vis[101000];
int ans=0,s[1010000];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),vis[a[i]]=i;
	for(int i=1;i<=n;i++) scanf("%d",&b[i]),b[i]=vis[b[i]];
	for(int i=1;i<=n;i++)
	{
		if(b[i]>s[ans]) s[++ans]=b[i];
		else
		{
			int l=1,r=ans,mid;
			while(l<r)
			{
				mid=(l+r)/2;
				if(s[mid]>b[i]) r=mid;
				else l=mid+1;
			}
			s[l]=b[i];
		}
	}
	printf("%d",ans);
	return 0;
}

4.股票市场

这道题竟然卡常，qwq,交了n多次。

第一种状转。（dp[v]直接存得到的钱数。）

#include<bits/stdc++.h>
using namespace std;
int s,tmp=0,d,m,p[55][11],dp[1000000],w[100];
int main()
{
	scanf("%d%d%d",&s,&d,&m);
	for(int i=1;i<=s;i++)
	for(int j=1;j<=d;j++)
	scanf("%d",&p[i][j]);
	for(int i=1;i<d;i++)
	{
		for(int j=1;j<=m;j++) dp[j]=j;
		for(int j=1;j<=s;j++)
		if(p[j][i]<p[j][i+1]) w[++tmp]=j;
		for(int j=1;j<=tmp;j++)
		{
			int h=w[j],b=p[h][i+1],a=p[h][i];
			for(int v=p[h][i],x;v<=m;v++)
			{
				x=dp[v-a]+b;
				if(x>dp[v]) dp[v]=x;
			}
		}
//		printf("%d\n",dp[m]);
		m=dp[m];
		tmp=0;
	}
	printf("%d",m);
	return 0;
}

第二种。（dp[v]存获得的利息）

#include<bits/stdc++.h>
using namespace std;
int s,d,m,p[55][11],dp[100000000];
int main()
{
    scanf("%d %d %d",&s,&d,&m);
    for(int i=1;i<=s;i++)
    for(int j=1;j<=d;j++)
    scanf("%d",&p[i][j]);
    for(int i=1;i<d;i++)
    {
        for(int j=1;j<=m;j++) dp[j]=0;
        for(int j=1;j<=s;j++)
        if(p[j][i]<p[j][i+1])
        for(int v=p[j][i];v<=m;v++)
        {
            dp[v]=max(dp[v],(dp[v-p[j][i]]+p[j][i+1]-p[j][i]));
        }
//		printf("%d\n",dp[m]);
        m+=dp[m];
    }
    printf("%d",m);
    return 0;
}

注意！！：

不能将dp[]清零！！！

5.树形DP

inline void dfs(int x,int fa)
{
	sz[x]=1;
	for(int i=head[x];i;i=edge[i].ne)
	{
		int to=edge[i].to;
		if(to!=fa) dfs(to,x);
		else continue;
		sz[x]+=sz[to];
	}
}//简单题1。 
inline void dfs(int x,int fa)
{
	sz[x]=w[x];
	for(int i=head[x];i;i=edge[i].ne)
	{
		int to=edge[i].to;
		if(to!=fa) dfs(to,x);
		else continue;
		sz[x]+=sz[to];
	}
}//简单题2。 
inline void dfs1(int x,int fa)
{
	for(int i=head[x];i;i=edge[i].ne)
	{
		int to=edge[i].to,w=edge[i].w;
		if(to==fa) continue;
		dfs(to,x);
		if(len1[to]+w>len1[x]) len1[x]=len1[to]+w;
		else if(len1[to]+w>len2[x]) len2[x]=len1[x]+w;
	}
}
inline void dfs2(int x,int fa)
{
	for(int i=head[i];i;i=edge[i].ne)
	{
		int to=edge[i].to,w=edge[i].w;
		if(to==fa) continue;
		if(len1[x]+w==len1[fa]) dis[x]=max(len1[x],len2[fa]+w);
		else dis[x]=max(len1[x],len1[fa]+w);
		dfs(to,x);
	}
}//简单题3；
inline void dfs(int x,int fa)
{
	sz[x]=1;
	int blance=0;
	for(int i=head[x];i;i=edge[i].ne)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		dfs(v,x);
		sz[x]+=sz[v];
		blance=max(blance,sz[v]);
	}
	blance=max(blance,n-sz[x]);
	if(blance<mn||(blance==mn&&x<ans1))
	mn=blance,ans1=x;
}
//简单题4；
//首先要知道什么是树的重心,树的重心定义为:找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡.  实际上树的重心在树的点分治中有重要的作用, 可以避免N^2的极端复杂度（从退化链的一端出发），保证
inline void dfs1(int x,int fa)
{
	for(int i=head[x];i;i=edge[i].ne)
	{
		int to=edge[i].to,w=edge[i].w;
		if(to==fa) continue;
		dfs(to,x);
		if(len1[to]+w>len1[x]) len1[x]=len1[to]+w;
		else if(len1[to]+w>len2[x]) len2[x]=len1[x]+w;
	}
	ans=max(len1[x]+len2[x],ans);
}
//简单题5

本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/98252bd5.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！