daily 2

CF 721 C

本来是需要三维，来记录一下当前经过的点集合，但是我们可以先把图分个层，然后就ok了，用top sort就可以了

void solve(){
  int n,m,T;
  cin>>n>>m>>T;
  vector<vector<int>>E(n+1);
  vector<vector<int>>cost(n+1);
  vector<int>in(n+1);
  for(int i=1;i<=m;++i){
    int u,v,w;
    cin>>u>>v>>w;
    in[v]++;
    E[u].push_back(v);
    cost[u].push_back(w);
  }
  vector bef(n+1,vector<int>(n+1,0)),dp(n+1,vector<int>(n+1,INF));
  dp[1][1]=0;
  bef[1][1]=-1;
  //dp[i][j] to be the j times left, and we are in i so dp[i][j]=dp[k][j+v_k]
  function<void()>topSort=[&](){
    queue<int>q;
    for(int i=1;i<=n;++i){
      if(!in[i]){
        q.push(i);
      }
    }
    while(!q.empty()){
      auto u=q.front();
      q.pop();
      for(int i=0;i<E[u].size();++i){
        int v=E[u][i],c=cost[u][i];
        --in[v];
        if(!in[v]){
          q.push(v);
        }
        for(int j=2;j<=n;++j){
          if(dp[v][j]>dp[u][j-1]+c){
            dp[v][j]=dp[u][j-1]+c;
            bef[v][j]=u;
          }
        }
      }
    }
  };
  topSort();
  function<void(int i,int j)>printTrace=[&](int i,int j){
    if(bef[i][j]==-1){
      cout<<i<<' ';
      return;
    }
    printTrace(bef[i][j],j-1);
    cout<<i<<' ';
  };
  for(int i=n;i>=1;--i){
    if(dp[n][i]<=T){
      cout<<i<<'\n';
      printTrace(n,i);
      break;
    }
  }
  return;
}

CF 1096D

void solve(){
  int n;
  cin>>n;
  string s;
  cin>>s;
  s=')'+s;
  map<char,int>mp;
  vector<int>a(n+1);
  vector dp(n+1,vector<int>(5));
  mp['h']=1,mp['a']=2,mp['r']=3,mp['d']=4;
  for(int i=1;i<=n;++i){
    cin>>a[i];
    for(int j=1;j<=4;++j){
        if(mp[s[i]]==j){
            if(j!=1){
                dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+a[i]);
            }else{
                dp[i][j]=dp[i-1][j]+a[i];
            }
        }else{
            dp[i][j]=dp[i-1][j];
        }
    }
  }
  cout<<dp[n][4]<<"\n";
  return;
}