題目是中文的，就直接貼過來了
眾所周知，我們可以通過直角坐標系把平面上的任何一個點P用一個有序數(shù)對(x, y)來唯一表示，如果x, y都是整數(shù)，我們就把點P稱為整點，否則點P稱為非整點。我們把平面上所有整點構成的集合記為W。
定義1 兩個整點P1(x1, y1), P2(x2, y2)，若|x1-x2| + |y1-y2| = 1，則稱P1, P2相鄰，記作P1~P2，否則稱P1, P2不相鄰。
定義 2 設點集S是W的一個有限子集，即S = {P1, P2,..., Pn}(n >= 1)，其中Pi(1 <= i <= n)屬于W，我們把S稱為整點集。
定義 3 設S是一個整點集，若點R, T屬于S，且存在一個有限的點序列Q1, Q2, ?, Qk滿足:
1. Qi屬于S（1 <= i <= k）;
2. Q1 = R, Qk = T;
3. Qi~Qi + 1(1 <= i <= k-1)，即Qi與Qi + 1相鄰;
4. 對于任何1 <= i < j <= k有Qi ≠ Qj;
我們則稱點R與點T在整點集S上連通，把點序列Q1, Q2,..., Qk稱為整點集S中連接點R與點T的一條道路。
定義4 若整點集V滿足：對于V中的任何兩個整點，V中有且僅有一條連接這兩點的道路，則V稱為單整點集。
定義5 對于平面上的每一個整點，我們可以賦予它一個整數(shù)，作為該點的權，于是我們把一個整點集中所有點的權的總和稱為該整點集的權和。
我們希望對于給定的一個單整點集V，求出一個V的最優(yōu)連通子集B，滿足：
1. B是V的子集
2. 對于B中的任何兩個整點，在B中連通；
3. B是滿足條件(1)和(2)的所有整點集中權和最大的。
Input
第1行是一個整數(shù)N（2 <= N <= 1000），表示單整點集V中點的個數(shù)；
以下N行中，第i行(1 <= i <= N)有三個整數(shù)，Xi, Yi, Ci依次表示第i個點的橫坐標，縱坐標和權。同一行相鄰兩數(shù)之間用一個空格分隔。-10^6 <= Xi, Yi <= 10^6；-100 <= Ci <= 100。
Output
僅一個整數(shù)，表示所求最優(yōu)連通集的權和。
這題和線性的最大子段和非常的類似，只不過改為了樹形而已，狀態(tài)轉移方程如下
dp[pos]=val[pos]+sum(dp[i]) i是pos的兒子且dp[i]>0。
可以和最大子段和的方程比較下
dp[i]=max{1,1+dp[i-1]}
貼代碼
1
# include <iostream>
2# include <cstdio>
3# include <cstring>
4using namespace std;
5# define abs(a) ((a)>0?(a):-(a))
6int x[1001],y[1001],val[1001];
7int g[1001];
8int v[2001],nxt[2001],c=0;
9int res=0;
10int dfs(int pos,int fa)
11
{
12
int maxnum=val[pos];
13 for(int p=g[pos];p!=-1;p=nxt[p])
14 if(v[p]!=fa)
15
{
16 int tmp=dfs(v[p],pos);
17 if(tmp>0) maxnum+=tmp;
18
}
19 maxnum=(maxnum>0?maxnum:0);
20 res=(maxnum>res?maxnum:res);
21 return maxnum;
22
}
23int main()
24{
25 int num;
26 scanf("%d",&num);
27 memset(g,-1,sizeof(g));
28 for(int i=0;i<num;i++)
29 {
30 scanf("%d%d%d",x+i,y+i,val+i);
31 for(int j=0;j<i;j++)
32 if(abs(x[i]-x[j])==1&&y[i]==y[j]||abs(y[i]-y[j])==1&&x[i]==x[j])
33 {
34 v[c]=j;
35 nxt[c]=g[i];
36 g[i]=c++;
37 v[c]=i;
38 nxt[c]=g[j];
39 g[j]=c++;
40 }
41 }
42 dfs(0,-1);
43 printf("%d\n",res);
44 //system("pause");
45 return 0;
46}
47
48