1018.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

//tree DP : f[i][j] =max( f[ lson[i] ][j-1] + lenl[i], f[ rson[i] ][j-1] +lenr[i], f[ lson[i] ][ k ]+lenl[i] + f[ rson[i] ][ j-k-2 ]+lenr[i] ) 
#include <iostream>
using namespace std;

const int maxN = 100;

int n , q;
int lson[maxN + 1],rson[maxN + 1], lenl[maxN + 1], lenr[maxN + 1];
int map[ maxN + 1 ][ maxN + 1];
bool isVisited[ maxN+1 ][ maxN+1 ];
int f[maxN+1][maxN + 1];
void readIn()
{
	memset( map,-1,sizeof(map) );
	memset( f,-1,sizeof(f) );
	int i,a,b;
	cin >> n >> q;
	for( i = 1; i<= n; i++ )
	{
		cin >> a >> b;
		cin >> map[a][b];
		map[b][a] = map[a][b];
	}
}
void dfs(int v)
{
	int i,j;
	for( i = 1 ; i <= n; i++ )
		if( map[v][i] != -1 && (isVisited[v][i]==false) ) { isVisited[v][i] = isVisited[i][v] = true; lson[v] = i,lenl[v] = map[v][i]; break; }

 	for( j=i+1 ; j <= n; j++ )
 		if( map[v][j] != -1 && (isVisited[v][j]==false) ) { isVisited[v][j] = isVisited[j][v] = true; rson[v] = j,lenr[v] = map[v][j]; break; }
	if( lson[v] ) dfs( lson[v] );
	if( rson[v] ) dfs( rson[v] );
}
void buildTree()
{
	for(int i = 1; i<= n; i++)
		isVisited[i][1] = true;
	/*	
	for( int i = 1; i<= n; i++ )
	{ for( int j = 1; j <= n; j++ )
		cout << map[i][j] <<  ' ' ;
	cout <<endl;
	
	}	*/
	 	dfs(1);
}

int max(int a, int b) {return a>b?a:b;}
int dp( int v, int q )
{
	int i;
	if( f[v][q] != -1 )return f[v][q];
	if( q == 0 )return f[v][q] = 0;
	if( q == 1 )return f[v][q] = max( lenl[v],lenr[v] );
	int temp = dp( lson[v],q-1 ) + lenl[v];
	temp = max(temp , dp( rson[v],q-1 ) + lenr[v] );
	for( i = 0; i <= q - 2; i++ )
	{
		temp  = max( temp, dp( lson[v], i )+ lenl[v] +dp( rson[v], q - i - 2 )+ lenr[v] );
	}
	f[v][q] = temp;
	return f[v][q];
}
int main()
{
	freopen("1018.in","r", stdin);
	readIn();

	buildTree();

	dp(1,q);

	cout << f[1][q] <<endl;
	return 0;
}