Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

dp最长上升序列变形+记录相同长度的数量

Posted by yuefanxiao at 2021-05-26 00:39:06 on Problem 3421
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
int x;
vector<int>factor;
int dp[1000];
int num[1000];
int main()
{
	while(~scanf("%d",&x))
	{
		factor.clear();
		for(int i=1;i*i<=x;++i)
		{
			if(x % i == 0)
			{
				factor.push_back(i);
				if(x/i != i)
					factor.push_back(x/i);
			}
		}
		sort(factor.begin(),factor.end());
		int SIZE = factor.size();
		int ansnum = 0;
		for(int i=0;i<SIZE;++i)
		{
			dp[i] = 1;
			num[i] = 1;
		}
		for(int i=0;i<SIZE;++i)
		{
			int maxlength = 0;
			for(int j=0;j<i;++j)
			{
				if(factor[i] > factor[j] && factor[i] % factor[j] == 0)
				{
					dp[i] = max(dp[i],dp[j] + 1);
					if(dp[i] > maxlength)
					{
						maxlength = dp[i];
						num[i] = num[j];
					}
					else if(dp[j] + 1 == maxlength)
					{
						num[i] += num[j];
					}
				}
			}
		}
		printf("%d %d\n",dp[SIZE-1]-1,num[SIZE-1]);
	}
	return 0;
} 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator