POJ 1770 Special Experiment G++ 例题 dfs动态规划 建图巧妙 背

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath> 
using namespace std;
//英语     看博友分析     抄博友程序      例题     dfs动态规划       建图巧妙     背 
vector<int> g[210];
int vis[210];
int dp[210][2];
int a[210],b[210];
void dfs(int u)//图 
{
	vis[u]=1;
	dp[u][0]=0;
	dp[u][1]=a[u];
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(vis[v]==0)
		{
			dfs(v);
			dp[u][0]+=max(dp[v][0],dp[v][1]);
			dp[u][1]+=dp[v][0];
		}
	}
}
int main()
{
	int n,m;
	while(1)
	{
		scanf("%d%d",&n,&m);
		if(n==0 && m==0)
		{
			break;
		}
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=n;i++)
		{
			g[i].clear();
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		for(int i=1;i<=m;i++)
		{
			scanf("%d",&b[i]);
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)
			{
				for(int k=1;k<=m;k++)
				{
					if(abs(a[i]-a[j])==b[k])
					{
						g[i].push_back(j);
						g[j].push_back(i);
					}
				}
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++)//不连通的图 
		{
			if(vis[i]==0)
			{
				dfs(i);
				ans+=max(dp[i][0],dp[i][1]);
			}
		}
		cout<<ans<<endl;		
	}
	return 0;
}