cf#156-C. Almost Arithmetical Progression-DP

72 阅读 0 评论 48 点赞

我是靠谱客的博主炙热小松鼠，最近开发中收集的这篇文章主要介绍cf#156-C. Almost Arithmetical Progression-DP，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

http://codeforces.com/problemset/problem/255/C

题意：

给n个数，找最长的交替串，形如 ABABABAB或者AAAAAAAA（可理解为B=A的特殊情况）

。。状态方程不太好想。。

对一个ABABABA串

dp[i][j]， i是串的最后一个数的位置，j是倒数第二个数的位置

那么，假设x=A[i];

dp[i][j]=dp[j][ last_pos[x] ]+1 (由前一个串递推过来)

其中last_pos[x]是指 A[i]这个数，上一次出现的位置（取最近）

我们枚举i的时候，1<=j<i, 那么我们只需要在枚举j时，遇到A[j]==A[i]，便令last_pos=j;

即：

for (i=1;i<=n;i++)
	{  
			int last=0;
		for (j=1;j<i;j++)
		{ 
			dp[i][j]=dp[j][last]+1;
			if (tm[i]==tm[j]) last=j; 
		} 
	}

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iostream>
using namespace std;
  
int dp[4005][4005]; 
int tm[4005]; 
int main(  )
{ 
	  int n;
	  cin>>n;
	  int j,i;
	  for (i=1;i<=n;i++) 
		  scanf("%d",&tm[i]);  
 

	//dp[i][j]表示i结尾，j为倒数第二元素
	int maxx=0,x,y;
	for (i=1;i<=n;i++)
	{  
			int last=0;
		for (j=1;j<i;j++)
		{ 
			dp[i][j]=dp[j][last]+1;
			if (tm[i]==tm[j]) last=j;
			if (dp[i][j]>maxx) maxx=dp[i][j]; 
		} 
	}
	maxx++;	//一个元素长度为1 
	printf("%dn",maxx);

    return 0;
}

第二次写的代码，离散化了

：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iostream>
using namespace std;

const double pi=acos(-1.0);
double eps=0.000001; 
 
__int64 max(__int64 a,__int64 b)
{return a>b?a:b;} 
 

int tm[4005],tmp[4005],dp[4005][4005];
map<int ,int >mp; 
int last[4005];
int main()
{
	 
	int i,j;
	int n;
	cin>>n;
	for (i=1;i<=n;i++)
	{
		scanf("%d",&tm[i]);
		tmp[i]=tm[i];
	}
	
	sort(tmp+1,tmp+1+n);
	
	int ok=0;
	for (i=1;i<=n;i++)
	{
		if (mp[tmp[i]]) continue;
		else mp[tmp[i]]=++ok;
	}
	for (i=1;i<=n;i++)
		tm[i]=mp[tm[i]];
	int maxx=0;
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=n;j++)
		{
			dp[i][j]=dp[last[j]][tm[i]]+1;
			maxx=max(maxx,dp[i][j]);
		}
		last[tm[i]]=i;
	}
	
	printf("%dn",maxx);

	
	
	
	
	return 0;
	
}