UOJ Logo yitengcheng的博客

博客

大家好,快乐链覆盖(899)那题我有一个疑问

2019-08-27 19:54:56 By yitengcheng

为什么dp数组要初始化到负无穷啊,不能初始化到0吗? 附上丑陋的代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int n,m,ans,ask;
int now;
int head[1000086];
struct node{
  int next,to;
}edge[1000086];
int dp[10086][506][3];
int tmp[506][3];
int size[100086],k,udp[506][3];
int vdp[506][3];
int x,y;
void add(int x,int y){
   now++;
   edge[now].to=y;
   edge[now].next=head[x];
   head[x]=now;
}
void dfs(int pos,int fa){
  /*  int udp[503][6] = dp[pos];
    udp[0][0]=0;
    udp[1][1]=1;
    udp[1][2]=1;
    size[pos]=1;
    for(int i=head[pos];i;i=edge[i].next){
      int v = edge[i].to;
      if(v == fa)continue;;
      dfs(v,pos);
      memset(udp,0,sizeof(udp));
      udp[0][0]=0;
      udp[1][1]=1;
      udp[1][2]=1;
       for(int s=0;s<=502;s++){
      for(int j=0;j<=2;j++){
        vdp[s][j]=dp[v][s][j];
    }
}
      for(int inu=0;inu<=min(k,size[pos])+1;inu++){
         for(int inv=0;inv<=min(k,size[v])+1;inv++){
              int vmax=max(vdp[inv][0],max(vdp[inv][1],vdp[inv][2]));
             if(inu+inv==0||inu+inv>k+1)continue;
             ndp[inu+inv][0]=max(ndp[inu+inv][0],udp[inu][0]+vmax);
             ndp[inu+inv][2]=max(ndp[inu+inv][2],udp[inu][2]+vmax);
             ndp[inu+inv][1]=max(ndp[inu+inv][1],udp[inu][1]+vmax);
             ndp[inu+inv][1]=max(ndp[inu+inv][1],udp[inu][0]+vdp[inv][1]+1);
             if(inu+inv-1>=1){
               ndp[inu+inv-1][2]=std::max(ndp[inu+inv-1][2],udp[inu][1]+vdp[inv][1]);
            }
        }
    }
     size[pos]+=size[v];
    }
  //memcpy(udp,ndp,sizeof(ndp));
  for(int i=0;i<=502;i++){
     for(int j=0;j<=2;j++){
        dp[pos][i][j]=ndp[i][j];
    }
}*/
  dp[pos][0][0]=0;
  dp[pos][1][1]=1;
  dp[pos][1][2]=1;
  size[pos]=1;
  for(int i=head[pos];i;i=edge[i].next){
    int v = edge[i].to;
    if(v == fa)continue;
    dfs(v,pos);
    memcpy(tmp,dp[pos],sizeof(dp[pos]));
    for(int inu=0;inu<=min(k,size[pos])+1;inu++){
      for(int inv=0;inv<=min(k,size[v])+1;inv++){
       if(inu+inv==0||inu+inv>k+1)continue;
       int vmax=max(dp[v][inv][0],max(dp[v][inv][1],dp[v][inv][2]));
       int u=pos;
       tmp[inu+inv][0]=max(tmp[inu+inv][0],dp[u][inu][0]+vmax);
       tmp[inu+inv][1]=max(tmp[inu+inv][1],dp[u][inu][1]+vmax);
       tmp[inu+inv][2]=max(tmp[inu+inv][2],dp[u][inu][2]+vmax);
       tmp[inu+inv][1]=max(tmp[inu+inv][1],dp[u][inu][0]+dp[v][inv][1]+1);
       if(inu+inv-1>=1){
         tmp[inu+inv-1][2]=max(tmp[inu+inv-1][2],dp[u][inu][1]+dp[v][inv][1]);u
     }
 }
}
  memcpy(dp[pos],tmp,sizeof(dp[pos]));
  size[pos]+=size[v];
}
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
    memset(dp,-0x3f,sizeof(dp));//0??
    ans=0;
    now=0;
    memset(head,0,sizeof(head));
    memset(size,0,sizeof(size));
    scanf("%d %d",&n,&k);
    for(int i=1;i<n;i++){
      scanf("%d %d",&x,&y);
      add(x,y);
      add(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=k;i++){
      ans=max(ans,max(dp[1][i][0],dp[1][i][2]));
     // printf("%d %d\n",dp[1][i][0],dp[1][i][2]);
    }
   // for(int i=1;i<=n;i++){
   //   printf("%d %d %d\n",i,dp[i][1][0],dp[i][1][2]);
 // }
    printf("%d\n",ans);
    puts("0");
}
    return 0;
}

评论

orzorz
%%%
  • 2019-08-30 20:22:43
interestingLSY
因为有些方案不存在,不能直接用来转移啊
  • 2019-08-31 21:35:18