文章

5

粉丝

100

获赞

2

访问

46.4k

头像
超简单DP,没意思
P1629 上海交通大学2019年机试题
发布于2021年2月28日 22:54
阅读数 12.8k

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
	int len, current;
	while(cin>>len){
		int dp[len+1][len+1], A[len+1];
		for(int i=0; i<len; i++) dp[0][i] = dp[i][0] = 0;
		for(int i=1; i<=len; i++) cin>>A[i];
		for(int j=1; j<=len; j++){
			cin>>current;
			for(int i=1; i<=len; i++){
				if(A[i] == current) dp[i][j] = dp[i-1][j-1]+1;
				else dp[i][j] = dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
		cout<<dp[len][len];
	}
} 

 

登录查看完整内容


登录后发布评论

2 条评论
User_test
2022年3月3日 19:27

这种方法在现在的用例中 已经超时了

赞(0)
曾派
2022年1月13日 19:36

不知道装什么 超简单 和我的一样只能跑40%的case

赞(3)