154
poj 1192 最優聯通子集 簡單dp
看起來和圖相關，其實就是個簡單dp，就和取最大連續和一樣，隻是在一顆樹中取……
有人說是樹狀dp，我也不知道是不是
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#define INF 1E9
using namespace std;
vector<int> near[1001];
int X[1001],Y[1001];
int value[1001];
int n,ans=-INF;
int now[1001];
int ok[1001];
int dfs(int v)
{
ok[v]=1;
now[v]=value[v];
for(int i=0;i<near[v].size();i++)
{
int u=near[v][i];
if(ok[u])continue;
dfs(u);
now[v]+=(now[u]>0?now[u]:0);
ans=max(ans,now[v]);
}
}
int main()
{
scanf("%d",&n);
int i,j;
for(i=0;i<n;i++)
{
scanf("%d%d%d",&X[i],&Y[i],&value[i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)continue;
if(fabs(X[i]-X[j])+fabs(Y[i]-Y[j])>1)continue;
near[i].push_back(j);
near[j].push_back(i);
}
}
dfs(0);
printf("%d\n",ans);
}
最後更新：2017-04-03 18:51:47