求助VIJOS咒语
  • 板块学术版
  • 楼主Coros_Trusds
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/4/16 20:48
  • 上次更新2023/11/5 00:28:36
查看原帖
求助VIJOS咒语
430409
Coros_Trusds楼主2021/4/16 20:48

萌新刚学DP,求助。。。

dp题,不知道为什么会错掉 ??????

P1624P1624 咒语

  • 问题描述
身为拜月教的高级间谍,你的任务总是逼迫你出生入死。比如这一次,拜月教主就派你跟踪赵灵儿一行,潜入试炼窟底。
据说试炼窟底藏着五行法术的最高法术:风神,雷神,雪妖,火神,山神的咒语。为了习得这些法术,要付出艰辛的努力,但是回报同样十分丰厚。
拜月希望你告诉他咒语的长度为多少,于是你偷偷躲在一边,想乘机看看咒语究竟是什么。突然,天空出现了两条非常长的数字串,你抓狂了。究竟哪个才是真正的咒语呢?你突然想到,这两个都不是咒语(不妨称之为伪咒语),而真正的咒语却与他们有着密切的联系。于是你打开拜月亲手给你写的纸条:"The Real Incantation is Their Common Increasing Subsequence of Maximal Possible Length(真的咒语是他们的最长上升公共子序列)"
"该死的拜月,居然还会E文!"你咒骂着,但为了一家老小的生命,又不得不卖命地算着咒语的长度。
  • 输入格式
第一行为1个数N,代表有N组测试数据。
对于每组测试数据,描述了两条数字串,首先一个数字为一条伪咒语的长度M,接下来M个数描述了伪咒语的内容。
  • 输出格式
共N行,每行一个数字,描叙了对应咒语的长度。
  • 样例输入
1
5 1 4 2 5 -12
4 -12 1 2 4
  • 样例输出
2
  • My Code:

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=10005;

const int ma=1000005;

int t;

int dp[maxn][maxn]; 

int a[ma],b[ma];

inline void init(int len_a,int len_b)
{
	for(register int i=1;i<=len_a;i++)
	{
		a[i]=0;
	}
	
	for(register int i=1;i<=len_b;i++)
	{
		b[i]=0;
	}
	
	for(register int i=1;i<=len_a;i++)
	{
		for(register int j=1;j<=len_b;j++)
		{
			dp[i][j]=0;
		}
	}
}

int main()
{
	scanf("%d",&t);
	
	while(t--)
	{
		int n,m;
		
		scanf("%d",&n);
		
		for(register int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		
		scanf("%d",&m);
		
		for(register int i=1;i<=m;i++)
		{
			scanf("%d",&b[i]);
		}
		
		for(register int i=1;i<=n;i++)
		{
			for(register int j=1;j<=m;j++)
			{
				if(a[i]==b[j])
				{
					dp[i][j]=dp[i-1][j-1]+1;
				}
				
				else
				{
					dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
				}
			}
		}
		
		printf("%d\n",dp[n][m]);
		
		init(n,m);
	}
	
	return 0;
}
2021/4/16 20:48
加载中...