題目是中文的，就直接貼過來了
眾所周知，我們可以通過直角坐標(biāo)系把平面上的任何一個(gè)點(diǎn)P用一個(gè)有序數(shù)對(x, y)來唯一表示，如果x, y都是整數(shù)，我們就把點(diǎn)P稱為整點(diǎn)，否則點(diǎn)P稱為非整點(diǎn)。我們把平面上所有整點(diǎn)構(gòu)成的集合記為W。
定義1 兩個(gè)整點(diǎn)P1(x1, y1), P2(x2, y2)，若|x1-x2| + |y1-y2| = 1，則稱P1, P2相鄰，記作P1~P2，否則稱P1, P2不相鄰。
定義 2 設(shè)點(diǎn)集S是W的一個(gè)有限子集，即S = {P1, P2,..., Pn}(n >= 1)，其中Pi(1 <= i <= n)屬于W，我們把S稱為整點(diǎn)集。
定義 3 設(shè)S是一個(gè)整點(diǎn)集，若點(diǎn)R, T屬于S，且存在一個(gè)有限的點(diǎn)序列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;
我們則稱點(diǎn)R與點(diǎn)T在整點(diǎn)集S上連通，把點(diǎn)序列Q1, Q2,..., Qk稱為整點(diǎn)集S中連接點(diǎn)R與點(diǎn)T的一條道路。
定義4 若整點(diǎn)集V滿足：對于V中的任何兩個(gè)整點(diǎn)，V中有且僅有一條連接這兩點(diǎn)的道路，則V稱為單整點(diǎn)集。
定義5 對于平面上的每一個(gè)整點(diǎn)，我們可以賦予它一個(gè)整數(shù)，作為該點(diǎn)的權(quán)，于是我們把一個(gè)整點(diǎn)集中所有點(diǎn)的權(quán)的總和稱為該整點(diǎn)集的權(quán)和。
我們希望對于給定的一個(gè)單整點(diǎn)集V，求出一個(gè)V的最優(yōu)連通子集B，滿足：
1. B是V的子集
2. 對于B中的任何兩個(gè)整點(diǎn)，在B中連通；
3. B是滿足條件(1)和(2)的所有整點(diǎn)集中權(quán)和最大的。
Input
第1行是一個(gè)整數(shù)N（2 <= N <= 1000），表示單整點(diǎn)集V中點(diǎn)的個(gè)數(shù)；
以下N行中，第i行(1 <= i <= N)有三個(gè)整數(shù)，Xi, Yi, Ci依次表示第i個(gè)點(diǎn)的橫坐標(biāo)，縱坐標(biāo)和權(quán)。同一行相鄰兩數(shù)之間用一個(gè)空格分隔。-10^6 <= Xi, Yi <= 10^6；-100 <= Ci <= 100。
Output
僅一個(gè)整數(shù)，表示所求最優(yōu)連通集的權(quán)和。
這題和線性的最大子段和非常的類似，只不過改為了樹形而已，狀態(tài)轉(zhuǎn)移方程如下
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