Uva(10859)(Placing Lampposts )

链接：https://vjudge.net/problem/UVA-10859
思路：还是一开始一点思路都没有啊，找不到状态转移，看了老刘的思路突然就感觉很清晰，这就是差距吧。到一个点有两种决策，放或者不放，如果不放必须是父节点有灯或者它本身为根节点（因为根节点不放的话他的子节点就一定会放，所以不存在照不到的情况），那么我们就用i表示当前节点，j表示父节点是否放灯，f表示他的父节点，那么先看能否不放，如果能遍历一遍他的子节点然后算出总和（这里注意可以让放一盏灯的权重高一点，按照老刘的书为2000，这样又可以记录下被两个灯都照到的路的数量，一举两得），然后再算放灯，遍历一遍然后算出总和，比较两个总和的大小取小的一个即可。注意要用一个vis数组记录当前状态是否已经查看过，用一个dp数组记录这个状态的值避免重复计算！
代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

int t,n,m,a,b;
vector<int> G[1010];
int vis[1010][2],dp[1001][2];

int dfs(int i,int j,int f){
    if(vis[i][j])return dp[i][j];//如果查看过，则返回值避免重复计算
    vis[i][j] = 1;
    int& ans = dp[i][j];//引用
    ans = 2000;//一盏灯权重为2000
for(int k=0;k<G[i].size();k++)
    if(G[i][k]!=f){
    ans+=dfs(G[i][k],1,i);
    }
    if(!j&&f>=0) ans++;//如果父节点存在并且点灯，则有两灯照的道路+1
    if(j||f<0){//如果为根节点或者父节点已经点灯
        int sum = 0;
        for(int k=0;k<G[i].size();k++)
            if(G[i][k]!=f)
                sum+=dfs(G[i][k],0,i);
        if(f>=0)sum++; 
        ans = min(ans,sum);
}
return ans;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)G[i].clear();
        for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
        }
        memset(vis,0,sizeof(vis));
        int ans = 0;
        for(int i=0;i<n;i++)//因为图有可能不连通，所以必须全部遍历
            if(!vis[i][0])
        ans+=dfs(i,0,-1);
    printf("%d %d %d\n",ans/2000,m-ans%2000,ans%2000);
    }
    return 0;
}

感叹一下差距真的大啊，再继续努力吧！！！