neoevoke » 2001 ICPC Taejon - D Human Gene Functions

2001 ICPC Taejon - D Human Gene Functions -

2009.06.02 15:02 neoevoke Edit

다이나믹 문제이다.

고도리가 열심히 옆에서 봐줘서 겨우 YES


#include <iostream>
#include <string.h>

using namespace std;

string a,b;

int cache[200][200];

int m[255];

int value[5][5]={{5,-1,-2,-1,-3},{-1,5,-3,-2,-4},{-2,-3,5,-2,-2},
	{-1,-2,-2,5,-1},{-3,-4,-2,-1,0}};

int func(char a,char b)
{
	return value[m[(int)a]][m[(int)b]];
}
int dyn(int i, int j)
{
	if(i==-1&&j==-1) return 0;
	if(i<0)
	{
		int sum=0;
		for(int t=0;t<=j;t++)
			sum+=func(' ',b[t]);
		return sum;
	}
	if(j<0)
	{
		int sum=0;
		for(int t=0;t<=i;t++)
			sum+=func(a[t],' ');
		return sum;
	}
	if(cache[i][j]!=-1) return cache[i][j];

	int &ret = cache[i][j];
	ret=dyn(i-1,j-1)+func(a[i],b[j]);
	ret=max(ret, dyn(i-1,j)+func(a[i],' '));
	ret=max(ret, dyn(i,j-1)+func(' ',b[j]));
	return ret;
}


int main()
{
	m[(int)'A']=0;
	m[(int)'C']=1;
	m[(int)'G']=2;
	m[(int)'T']=3;
	m[(int)' ']=4;
	int t;
	cin >> t;
	while(t--)
	{
		int an,bn;
		cin >> an >> a;
		cin >> bn >> b;
		memset(cache,-1,sizeof(cache));

		cout << dyn(an-1,bn-1) << endl;
	}
}

Filezilla Server 설치&설정 하는 법 2001 ICPC Taejon - Modular multiplication of polynomials

Trackbacks 0

엮인글 주소: http://dw.yutar.net/328949/70c/trackback

Comments 1

소름

2011.12.18 19:32

*.14.240.111
문제의미를 잘 모르겠는데요.
+5점 -1,-2,-3점 이런 점수들은 어떻게 나오는건가요?

비밀번호 :

비밀번호 :

Leave Comments

neoevoke소셜계의 김성모

Category

전체글 (166)

기본 카테고리 (3)
일상 (9)
Code (49)
- usaco (40)
- topcoder (1)
Work (4)
맛집 (4)
- 일식 (1)
- 한식
- 학교식당 (2)
- 양식
미투데이 (23)
Util (3)
- Windows7 (1)
여행 (13)
- 제주도 (13)
펌 (8)
분류 전체보기
블로그리뷰 (1)
Study (4)
- 경제 (2)
- 의료 (1)
- Objective-C (1)
운동 (11)
- 트라이애슬론 (11)
- 스노우보드

Recent Post

[발번역] 고백 : 눈물 콧물... 2011-12-20 11:51
Objective-C ARC에 대한 이... ⁶ 2011-11-27 18:00
수영 - 500m 2011-07-30 11:31
기본으로 돌아가자 2011-07-28 00:48
수영 원포인트 2011-07-27 00:25
수영 2011-07-26 08:43
자전거 2011-07-24 23:03
수영 - 자유형 적절한 호흡 ... 2011-07-23 22:26
수영 5일째 2011-07-19 09:34
수영 4일째 ² 2011-07-16 21:34

Recent Comment

Recent Trackback

Tag

T-NAVI