uva:111-History Grading

テーマリンク:http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=114&page=show_problem&problem=47
LCS問題：動き方程式：dp[i][j]=dp[i-1]、[j-1]+1（numx[i]=numy[j]）𞓜max{dp[i-1]、[j]，dp[i]、[i]、[j-1]]
この問題の意味に注意して、人をめぐって、データを見ている時に感じがおかしいです。それから、問題をよく見て、入力された一連の数字は、対応桁iの上の数a[i]が第iの出来事の発生時間を表しています。
コードは以下の通りです

#include
#include
#include

using namespace std ;

const int maxn = 25 ;

int n;
int numx[maxn] ;
int numy[maxn] ;
int dp[maxn][maxn] ;

int main()
{
	//freopen("data.in" , "r" , stdin) ;

	int i ;
	int j ;
	int x ;

	cin>>n;

	for(i = 1 ; i <= n ; i ++)
	{
		cin>>x ;
		numx[x] = i ;
	}

	while(cin>>x)
	{
		numy[x] = 1 ;

		for(j = 2 ; j <= n ; j ++)
		{
			cin>>x ;
			numy[x] = j ;
		}

		memset(dp , 0 , sizeof(dp)) ;

		for(i = 1 ; i <= n ; i ++)
		{
			for(j = 1 ; j <= n ; j ++)
			{
				if(numx[i]==numy[j])
					dp[i][j] = dp[i-1][j-1] + 1 ;
				else
					dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1] ;
			}
		}

		printf("%d
" , dp[n][n]) ;
	}

	return 0 ;
}

私は先ほど記憶化検索の方式でこのテーマを提出しました。初期化の時は-1に初期化するべきです。でないと、エラーが発生します。コードは下記の通りです。

#include
#include
#include

using namespace std ;

const int maxn = 1005 ;

char numa[maxn] ;
char numb[maxn] ;
int  num[maxn][maxn] ;

int lena ;
int lenb ;

int dp(int , int ) ; 
int main()
{
	//freopen("data.in" , "r" , stdin) ;

	while(1)
	{
		cin.getline(numa , sizeof(numa)) ;
		if(!cin)
			break ;
		cin.getline(numb  , sizeof(numb)) ;
		
		lena = strlen(numa ) ;
		lenb = strlen(numb ) ;

		memset(num , -1 , sizeof(num)) ;

		dp(lena - 1 , lenb - 1) ;

		printf("%d
" , num[lena-1][lenb-1]) ;
	}
	return 0 ;
}

int dp(int n , int m)
{
	int & ans = num[n][m] ;
	
	if(n < 0 || m < 0)
		return 0 ;

	if(ans >= 0)
	{
		return ans ;
	}

	if(numa[n]==numb[m])
	{
		ans = dp(n - 1 , m - 1) + 1 ;
	}

	else if(dp(n-1 , m) >= dp(n , m - 1))
	{
		ans = dp(n-1 , m) ;
	}
	else ans = dp(n , m - 1) ;

	return ans ;
}