zoj 3160

11月19号准备做的题。。。拖了2个月。。。。

http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=17253#problem/G

还是想清楚再敲码，不然后面再修修补补容易出错。。。

#include<iostream>
#include<stdio.h>

using namespace std;
int f[304][304];
int data[304];
bool judge[304][304];

int main( ) 
{
	int n,m;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
			{
				judge[i][j]=false;
				f[i][j]=0;
			}
		for(int i=0;i<m;i++)
		{
			int x,y;
			scanf("%d %d",&x,&y);
			judge[x][y]=judge[y][x]=true;
		}
		for(int i=0;i<n;i++)
		{
			f[i][i]=0;
			scanf("%d",&data[i]);
		}
		for(int i=0;i<n-1;i++)
		{
			if(judge[data[i]][data[i+1]])
				f[i][i+1]=2;
		}
		for(int r=2;r<n;r++)
		{
			for(int i=0;i+r<n;i++)
			{
				int j=i+r;
				bool tmpjudge = judge[data[i]][data[j]];
				for(int k=i;k<j;k++)
				{
					int tmp=f[i][k]+f[k+1][j];
					if(f[i+1][k]+f[k+1][j-1]==j-i-1&&tmpjudge)
						tmp=tmp+2;
					if(tmp>f[i][j])
						f[i][j]=tmp;
				}
			}
		}
		printf("%d\n",f[0][n-1]);
	}
	//system("pause");
	return 0;
}