daily 3

一道水题，两道状压

CF 597B

简单贪心，按照结束时间排序即可

struct node{
    int l,r;
};
void solve(){
  int n;cin>>n;
  vector<node>a(n);
  for(int i=0;i<n;++i){
    cin>>a[i].l>>a[i].r;
  }
  sort(a.begin(),a.end(),[&](node a,node b){
    if(a.r==b.r)return a.l<b.l;
    return a.r<b.r;
  });
  int ans=0,last=-1;
  for(auto& k:a){
    if(k.l>last){
        ++ans;
        last=k.r;
    }
  }
  cout<<ans<<'\n';
  return;
}

CF 580D

简单状态压缩

${dp[status][i]}$ 表示当前吃了的是status,当前遇到的是i

转移也很简单

void solve(){
  int n,m,k;
  cin>>n>>m>>k;
  vector<int>a(n);
  vector<vector<int>>mp(n+1,vector<int>(n+1));
  vector dp((1<<n),vector<ll>(n));
  for(int i=0;i<n;++i){
    cin>>a[i];
    dp[1<<i][i]=a[i];
  }
  for(int i=0;i<k;++i){
    int u,v,c;
    cin>>u>>v>>c;
    --u,--v;
    mp[u][v]=c;
  }
  for(int status=0;status<(1<<n);++status){
    for(int i=0;i<n;++i){
        if(status&(1<<i)){
            for(int j=0;j<n;++j){
                if(i!=j&&(status&(1<<j))){
                    dp[status][i]=max(dp[status][i],dp[status^(1<<i)][j]+a[i]+mp[j][i]);
                }
            }
        }
    }
  }
  ll ans=0;
  for(int status=0;status<(1<<n);++status){
    if(__builtin_popcount(status)!=m)continue;
    for(int i=0;i<n;++i){
        if(status&(1<<i)){
            ans=max(ans,dp[status][i]);
        }
    }
  }
  cout<<ans<<'\n';
  return;
}

CF 53E

和上面的题思路差不多
${dp[status][leaf]}$ 表示当前的点集以及当前的叶子集合

void solve(){
  int n,m,k;
  cin>>n>>m>>k;
  int lim=1<<n;
  vector<vector<int>>E(n);
  for(int i=0;i<m;++i){
    int u,v;
    cin>>u>>v;
    --u,--v;
    E[u].push_back(v);
    E[v].push_back(u);
  }
  vector dp(lim,vector<int>(lim));
  vector<int>cnt(lim+1);
  for(int i=0;i<lim;++i){
    cnt[i]=__builtin_popcount(i);
  }
  for(int i=1;i<lim;i<<=1){
    dp[i][i]=1;
  }
  for(int total=0;total<lim;++total){
    for(int leaf=total;leaf;--leaf&=total){
        if(dp[total][leaf]){
            for(int now_node=0;now_node<n;++now_node){
                if(total&(1<<now_node)){
                    for(int new_node:E[now_node]){
                        if(!(total&(1<<new_node))){
                            int status;
                            if(cnt[total]==1){
                                status=total|(1<<new_node);
                            }else{
                                status=leaf&~(1<<now_node)|(1<<new_node);
                            }
                            if(!(status>>new_node+1)){//why？
                                dp[total|(1<<new_node)][status]+=dp[total][leaf];
                            }
                        }
                    }
                }
            }
        }
    }
  }
  ll ans=0;
  for(int i=0;i<lim;++i){
    if(cnt[i]==k){
        ans+=dp[lim-1][i];
    }
  }
  cout<<ans<<'\n';
  return;
}

作息不能乱！作息不能乱！作息不能乱！作息不能乱！作息不能乱！作息不能乱！作息不能乱！