学步园

所谓状态机背包：

•  一个背包，有n种状态。状态k，对应背包中装入了[ai_k,bi_k]个物品i。
• 那么状态之间切换：状态k=》装入物品i=》状态j。
• 注意，状态之间甚至可以互相包含。
• 则一般的状态递推过程：
• for 物品槽i=1 to weight:
•     for 状态s=1 to n:
•         for 物品obj=1 to m:
•               num[s]=>obj=>num[s1] //装包过程是一次状态切换，同时也是一次动规DP

递推方程：

    下面的递推方程：

    物品抽象为：[x,y]或[x]，x为是否带车进入点root， y为是否带车返回到点root， [0,0]为不带车进入root，并不带车退回到root。

    state[1]： 背包中仅装入[0,0]和一个以内的[0] 

    state[2]:    背包中仅装入[0,0]

    state[3]： 背包中装入[0,0] [1,1]；一个以内的[0]或[1,0], 抑或一个以内的[1]

    state[4]:    背包中装入[0,0] [1,1]；一个以内的[1,0]

    state[5]:    背包中装入[0,0][1,1]; 

    state[6]:    背包中装入[0,0][1,1]；一个以内的[0]

    state[1~6]对应下面代码里的x1~x6,y1~y6,z1~z6

#include<iostream>
#include <stdio.h>
#include <vector>
#include <map>
#define MAXN 1000000
#define mpr(a,b,c) make_pair(a,make_pair(b,c))
#define cmin(a,b) if(a>b) a=b;
using namespace std;
typedef long long int ll;
typedef pair<int,pair<int,int> > Pair;


ll num[MAXN][6];


inline ll min4(ll a,ll b,ll c,ll d) {
  ll tmp=(a<b?a:b);
  tmp=(tmp<c?tmp:c);
  tmp=(tmp<d?tmp:d);
  return tmp;
}


void dp(vector<vector<Pair> > &tree,ll num[][6],int fa,int root){
  //[people back][car in][car back]
  //car in means car start at root, car back means car stop at root
  //
  ll y1=0,y2=0,y3=0,y4=0,y5=0,y6=0;
  for(int i=0;i<tree[root].size();i++){
    Pair &p=tree[root][i];
    int son=p.first,c0=p.second.first,c1=p.second.second;
    if(son==fa||son==-1) continue;
    dp(tree,num,root,son);


    ll x1,x2,x3,x4,x5,x6;
    //[people][car in][car back]
    ll z1=num[son][0];//[0][0][0]
    ll z2=num[son][1];//[1][0][0]
    ll z3=num[son][2];//[0][1][0]
    ll z4=num[son][3];//[1][1][0]
    ll z5=num[son][4];//]1][1][1]


    x1=min(
        y1+(z2+2*c0), 
        y2+(z1+c0)
        ); 
    x2=y2+z2+2*c0;
    //state 4,5,6 working for state 3
    x4=min(
        y4+min(z2+2*c0,z5+2*c1), 
        y5+(z4+c1+c0)
        ); 
    x5=y5+min(z2+2*c0,z5+2*c1);
    x6=min(
        y6+min(z2+2*c0,z5+2*c1),
        y5+(z1+c0)
        );
    x3=min4(
        y3+min(z2+2*c0,z5+2*c1), 
        y4+(z1+c0),  
        y5+(z3+c1), 
        y6+(z4+c1+c0) 
        );
    
    y1=x1; y2=x2; y3=x3; y4=x4; y5=x5; y6=x6;
  }
  num[root][0]=y1;
  num[root][1]=y2;
  num[root][2]=y3;
  num[root][3]=y4;
  num[root][4]=y5;
}


bool dfsCut(int fa,int root, vector<vector<Pair> > &tree,vector<bool> &nodes){
  bool cut=nodes[root];
  for(int i=0;i<tree[root].size();i++){
    Pair &p=tree[root][i];
    int son=p.first;
    if(son==fa) continue;
    if(!dfsCut(root,son,tree,nodes))
      p.first=-1;//cut this
    else cut=true;
  }
  return cut;
}


int main(){
  int n;scanf("%d",&n);
  vector<vector<Pair> > tree(n,vector<Pair>());
  for(int i=0;i<n-1;i++){
    int a,b,c0,c1;scanf("%d%d%d%d",&a,&b,&c0,&c1);a--,b--;
    tree[a].push_back(mpr(b,c0,c1));
    tree[b].push_back(mpr(a,c0,c1));
  }
  int m;scanf("%d",&m);
  vector<bool> nodes(n,false);
  for(int i=0;i<m;i++){
    int a;scanf("%d",&a);a--;
    nodes[a]=true;
  }
  dfsCut(-1,0,tree,nodes);


  int root=0;
  dp(tree,num,-1,root);
  printf("%d\n",num[root][2]);


  return 0;
}

旧版本代码存在两个问题：

• 1 最后输出printf("%d\n",num[root][2]),打印语句会有int溢出 printf int overflow, should be "%lld\n"！！！
• 2 没必要把states存在num[][]里面，直接把states通过dp/dfs()返回就好了！因为本题的递推方程一次只用到了一个子节点，所以没必要记忆所有states到[]
  • void dfs(env[],&results[],&current_result[],current_idx,&maxV)  //不返回类型dfs
  • 或者 res_type dfs(env[], current_idx, &maxV) //返回类型dfs

#include<iostream>
#include <stdio.h>
#include <vector>
#include <map>
#define MAXN 1000000
#define mpr(a,b,c) make_pair(a,make_pair(b,c))
#define cmin(a,b) if(a>b) a=b;
using namespace std;
typedef long long int ll;
typedef pair<int,pair<int,int> > Pair;


inline ll min4(ll a,ll b,ll c,ll d) {
  ll tmp=(a<b?a:b);
  tmp=(tmp<c?tmp:c);
  tmp=(tmp<d?tmp:d);
  return tmp;
}
struct state{
  ll z1,z2,z3,z4,z5;
  state(ll a,ll b,ll c,ll d,ll e):z1(a),z2(b),z3(c),z4(d),z5(e){}
};
state dp(vector<vector<Pair> > &tree,int fa,int root){
  //[people back][car in][car back]
  //car in means car start at root, car back means car stop at root
  ll y1=0,y2=0,y3=0,y4=0,y5=0,y6=0;
  for(int i=0;i<tree[root].size();i++){
    Pair &p=tree[root][i];
    int son=p.first,c0=p.second.first,c1=p.second.second;
    if(son==fa||son==-1) continue;
    state s=dp(tree,root,son);

    //[people][car in][car back]
    ll x1,x2,x3,x4,x5,x6;
    ll z1=s.z1,z2=s.z2,z3=s.z3,z4=s.z4,z5=s.z5;

    x1=min(
        y1+(z2+2*c0), 
        y2+(z1+c0)
        ); 
    x2=y2+z2+2*c0;
    //state 4,5,6 working for state 3
    x4=min(
        y4+min(z2+2*c0,z5+2*c1), 
        y5+(z4+c1+c0)
        ); 
    x5=y5+min(z2+2*c0,z5+2*c1);
    x6=min(
        y6+min(z2+2*c0,z5+2*c1),
        y5+(z1+c0)
        );
    x3=min4(
        y3+min(z2+2*c0,z5+2*c1), 
        y4+(z1+c0),  
        y5+(z3+c1), 
        y6+(z4+c1+c0) 
        );
    
    y1=x1; y2=x2; y3=x3; y4=x4; y5=x5; y6=x6;
  }
  return state(y1,y2,y3,y4,y5);
}

bool dfsCut(int fa,int root, vector<vector<Pair> > &tree,vector<bool> &nodes){
  bool cut=nodes[root];
  for(int i=0;i<tree[root].size();i++){
    Pair &p=tree[root][i];
    int son=p.first;
    if(son==fa) continue;
    if(!dfsCut(root,son,tree,nodes))
      p.first=-1;//cut this
    else cut=true;
  }
  return cut;
}

int main(){
  int n;scanf("%d",&n);
  vector<vector<Pair> > tree(n,vector<Pair>());
  for(int i=0;i<n-1;i++){
    int a,b,c0,c1;scanf("%d%d%d%d",&a,&b,&c0,&c1);a--,b--;
    tree[a].push_back(mpr(b,c0,c1));
    tree[b].push_back(mpr(a,c0,c1));
  }
  int m;scanf("%d",&m);
  vector<bool> nodes(n,false);
  for(int i=0;i<m;i++){
    int a;scanf("%d",&a);a--;
    nodes[a]=true;
  }
  dfsCut(-1,0,tree,nodes);

  int root=0;
  state s=dp(tree,-1,root);
  printf("%lld\n",s.z3);//@error: "%d\n"

  return 0;
}