动态规划 Interesting Tour hdu 3562

题目大意：初始集合有3点且互相连通，然后不断的加入n-3个新点，每个点与原来集合中的2个点相连，保证这两点已经相连，边都是双向的（这个地方wa了两次），问从其中的任意点出发，每条边和每个点都只走一次且最后回到初始点总共能访问多少个点。求最多的访问点数。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3562

题目分析：这个题刚开始时没有注意到与新点相连的两个点已保证相连，所以没思路，参考了别人的代码，总感觉是错误的，后来又自习读了一遍题目，才发现，所以就做掉了。后面加入的点对前面已存在的点没有影响，所以只需从后往前枚举加入的点，然后把后面点的联通情况想前推，最终归根在初始的三点上。只要明白了思路这个题就比较简单了。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=1004;
int dp[maxn][maxn];//dp[i][j]表示idaoj需要经过的点数不包括i和j
int data[maxn][2];//记录与i相连的两个点

int main(){
    int n,a,b;
    while(scanf("%d",&n)!=EOF){
        memset(dp,0,sizeof(dp));
        for(int i=4;i<=n;i++){
            scanf("%d%d",&a,&b);
            data[i][0]=a;
            data[i][1]=b;
        }
        int ans=0;
        for(int i=n;i>=4;i--){
            a=data[i][0];
            b=data[i][1];
            ans=max(ans,dp[a][b]+dp[a][i]+dp[i][b]+3);
            dp[a][b]=dp[b][a]=max(dp[a][b],dp[a][i]+dp[i][b]+1);//这个地方注意dp[a][b]=dp[b][a]=max(),wa了两次
        }
        printf("%d\n",max(ans,dp[1][2]+dp[2][3]+dp[1][3]+3));
    }
    return 0;
}