|Vijos|동적 기획 |P1111 뚱뚱한 과일

747 단어 동적 기획Vijos
https://vijos.org/p/1111
LCS, (두 문자열의 총 길이-두 문자열이 구한 LCS)는 바로 답입니다. 입력한 문자는 0으로 시작하는데 dp에서 0-1은 경계를 넘을 수 있습니다. 입력할 때 입력한 문자의 바늘을 a로 가리키지 말고 a+1을 가리키십시오.
#include
#include  
#include   
#include 
#define ms(i,j) memset(i, j, sizeof(i)); 
using namespace std;
char a[105], b[105];
int f[105][105];
int main()  
{
	while (scanf("%s%s", a+1, b+1)==2)
	{
		ms(f,0);
		int l1 = strlen(a+1), l2 = strlen(b+1); 
		for (int i=1;i<=l1;i++)
		for (int j=1;j<=l2;j++)
		{
			if (a[i]==b[j]) f[i][j] = f[i-1][j-1]+1;
			    else f[i][j] = max(f[i-1][j], f[i][j-1]);
		}
		printf("%d
", l1+l2-f[l1][l2]); } return 0; }

좋은 웹페이지 즐겨찾기