daily 3

2023/4/1 daily

CF 413C

令 dp[i][0/1]表示当前总和为i，且含有/不含有大于d的值

那么对于枚举的边权j

若j>=d;

${dp[i][1]+=dp[i-j][0]+dp[i-j][1]}$

若j<d

${dp[i][0]+=dp[i-j][0]}$

${dp[i][1]+=dp[i-j][1]}$

ll dp[N][2];
void solve(){
  int n,k,d;
  cin>>n>>k>>d;
  dp[0][0]=1;
  for(int i=1;i<=n;++i){
    for(int j=1;j<=k;++j){
        if(i-j<0)break;
        if(j>=d){
            dp[i][1]=(dp[i][1]+(dp[i-j][0]+dp[i-j][1])%MOD)%MOD;
        }else{
            dp[i][0]=(dp[i][0]+(dp[i-j][0]))%MOD;
            dp[i][1]=(dp[i][1]+dp[i-j][1])%MOD;
        }
    }
  }
  cout<<dp[n][1]<<'\n';
  return;
}

CF 417D

状态压缩

首先装压很好想，之后就是这个买monitor的问题，我们可以按照monitor从少到多排序，然后每次更新ans的时候只和dp[(1<<m)-1]来比就ok了

const int MOD=1e9+7;
const ll INF=1100000020000000000;
struct f{
    int x,k,sta;
};
void solve(){
  int n,m,b;
  cin>>n>>m>>b;//number of friend number of problems and number of cost for a single monitor
  vector<f>fri(n);
  for(int i=0;i<n;++i){
    int xi,ki,mi;//money the friend needs,monitor needs and number of problem the friend could solve
    cin>>xi>>ki>>mi;
    int sta=0;
    for(int j=0;j<mi;++j){
        int t;cin>>t;
        --t;
        sta|=(1<<t);
    }
    fri[i]={xi,ki,sta};
  }
  sort(fri.begin(),fri.end(),[&](f a,f b){
    return a.k<b.k;
  });
  vector<ll>dp(1<<m,INF);
  dp[0]=0;
  ll ans=INF;
  for(int i=0;i<n;++i){
    for(int j=0;j<(1<<m);++j){
        if(dp[j]<INF){
            dp[j|fri[i].sta]=min(dp[j|fri[i].sta],dp[j]+fri[i].x);
        }
    }
    ans=min(ans,dp[(1<<m)-1]+1ll*fri[i].k*b);
  }
  cout<<(ans>=INF?-1:ans)<<'\n';
  return;
}

CF 11D
另一道装压
dp[sta][id]表示当前经过的点状态集合为sta，当前的点为id的情况
记得转移的时候要减去m，因为这m条边多算了（重边），然后二元以上的环会多算

#define lowbit(x) (x&-x)
void solve(){
  int n,m;
  cin>>n>>m;
  vector<vector<ll>>dp(1ll<<n,vector<ll>(n));
  vector<vector<int>>mp(n,vector<int>(n));
  for(int i=0;i<m;++i){
    int u,v;
    cin>>u>>v;
    --u,--v;
    mp[u][v]=mp[v][u]=1;
  }
  ll ans=0;
  for(int i=0;i<n;++i)dp[1<<i][i]=1;
  for(int sta=0;sta<(1<<n);++sta){
    for(int id=0;id<n;++id){
        if(!dp[sta][id]){
            continue;
        }
        for(int k=0;k<n;++k){
            if(!mp[id][k])continue;
            if(lowbit(sta)>(1<<k))continue;
            if(1<<k&sta){
                if(1<<k==lowbit(sta)){
                    ans+=dp[sta][id];
                }
            }else{
                dp[sta|(1<<k)][k]+=dp[sta][id];// if did not run on it then walk!
            }
        }
    }
  } 
  cout<<((ans-m)>>1)<<'\n';//minus the common road 
  return;
}

感觉有点懒散了，不能酱紫了，待会跑一跑miniob,然后明天估计得看一下设计模式

LOADING

daily 3