题意: 一个能量E可以通过吸收某个光子的能量变成E1或者释放某个光子的能量变成E2...并且任意两个能量的转化路径至多一条...现在有一堆能量,有一堆光子...如果某个能量与某个光子做
题意: 一个能量E可以通过吸收某个光子的能量变成E1或者释放某个光子的能量变成E2...并且任意两个能量的转化路径至多一条...现在有一堆能量,有一堆光子...如果某个能量与某个光子做直接运算(加上其能量或者减去)会等于一个已经存在的能量...那么就会发生危险...问在这堆能量中..不发生危险并且能量和最大为多少...
由于两个能量的转化路径至多一条..那么可以用树(森林)来表示所有的关系...有冲突的两点做无向边....我之前一直WA就是做成有向边了...
dp[k][0]代表以k为根的子树,不取k这个点..最多能获得的能量...
dp[k][1]代表以k为根的子树,取k这个点..最多能获得的能量...
转化成一个很经典的问题了..
Program:
#include<iostream>#include<stack>
#include<queue>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<cmath>
#define ll long long
#define oo 1000000007
#define MAXN 205
using namespace std;
vector<int> Tree[MAXN];
int n,m,a[MAXN],dp[MAXN][2];
bool P[1000005],used[MAXN],root[MAXN];
void dfs(int x)
{
int i,num=Tree[x].size();
used[x]=true;
dp[x][0]=0,dp[x][1]=a[x];
for (i=0;i<num;i++)
if (!used[Tree[x][i]])
{
dfs(Tree[x][i]);
dp[x][0]+=max(dp[Tree[x][i]][0],dp[Tree[x][i]][1]);
dp[x][1]+=dp[Tree[x][i]][0];
}
return;
}
int main()
{
int i,x;
while (~scanf("%d%d",&n,&m) && (n || m))
{
for (i=1;i<=n;i++) scanf("%d",&a[i]),Tree[i].clear();
sort(a+1,a+1+n);
memset(P,false,sizeof(P));
P[0]=true;
for (i=1;i<=m;i++) scanf("%d",&x),P[x]=true;
memset(root,true,sizeof(root));
for (i=1;i<=n;i++)
for (x=i+1;x<=n;x++)
if (P[a[x]-a[i]])
Tree[x].push_back(i),Tree[i].push_back(x);
memset(used,false,sizeof(used));
x=0;
for (i=1;i<=n;i++)
if (!used[i])
{
dfs(i);
x+=max(dp[i][0],dp[i][1]);
}
printf("%d\n",x);
}
return 0;
}