牛客多校第二场B discount 基环内向树

题意：

有n种商品，每种商品有一个价格 p[i] 。

每种商品都有2种打折方式：

1. 给你优惠 d[i] 元。

2. 免费送你第 f[i] 种饮料。

现在求每种饮料至少一瓶的最小花费。

dp[i][0] 表示 i 的子树内所有的饮料都至少买了一瓶。

dp[i][1] 表示 i 的子树内所有的饮料都至少买了一瓶且第i种饮料是使用第2种方式购买的。

我们考虑树的转移方式。

sum[i] 表示 dp[son[i]][0] 的和

dp[i][1] = sum[i] + p[i]

dp[i][0] = min(p[i]-d[i]+sum[i], sum[i] - dp[son[i][0] + dp[son[i][1] )

然后我们可以先把环都抠出来，然后将环上的边都标记一下，

然后先把环的子树都转移到环上来，最后再处理环的问题。

假设一个环为 a -> b -> c -> d -> a ，mn 为这个环的最小花费。

我们断开a -> b 这条边，并且 b 不是通过 a 送来的。

G[0][0] = dp[b][0] G[0][1] = dp[b][1]

路上转移的状态为 G[1][1] = dp[c][1] + G[0][0];

G[1][0] = min(G[0][1]+sum[c], dp[c][0] + G[0][0])

这样一直转移到G[3][0]

因为我们规定b 不是通过 a 送来的。 mn = min(mn, G[3][0])

然后我们假设 b 是通过 a 送过来的

G[0][0] = sum[b] G[0][1] = dp[b][1]

然后通过上面的转移方程转移到G[3][1]。

因为b是a送的那么 a 必须要按方式1购买所以 mn = min(mn, G[3][1])

最后将 mn 加入答案中。

然后跑完所有环之后就能得到答案了。

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod =  (int)1e9+;

 const int N = 1e5 + ;

 int p[N], d[N], f[N];

 int head[N], to[N], nt[N];

 int vis[N];

 int cntCir = , tot = , top, n;

 int sta[N];

 vector<int> cir[N];

 int vvis[N];

 LL dp[N][];

 LL sum[N];

 LL G[N][];

 void add(int u, int v){

     to[tot] = v;

     nt[tot] = head[u];

     head[u] = tot++;

 }

 void getCir(int u){

     if(vis[u] == ) return ;

     if(vis[u] == -){

         cntCir++;

         for(int i = top; i >= ; i--){

             cir[cntCir].pb(sta[i]);

             vvis[sta[i]] = ;

             if(sta[i] == u) break;

         }

         return;

     }

     vis[u] = -;

     sta[++top] = u;

     getCir(f[u]);

     top--;

     vis[u] = ;

 }

 void dfs(int u){

     for(int i = head[u]; ~i; i = nt[i]){

         if(vvis[to[i]]) continue;

         dfs(to[i]);

         sum[u] += dp[to[i]][];

     }

     dp[u][] = sum[u] + p[u];

     dp[u][] = sum[u] + p[u] - d[u];

     for(int i = head[u]; ~i; i = nt[i]){

         if(vvis[to[i]]) continue;

         dp[u][] = min(dp[u][], sum[u] - dp[to[i]][] + dp[to[i]][]);

     }

 }

 int main(){

     memset(head, -, sizeof(head));

     scanf("%d", &n);

     for(int i = ; i <= n; i++) scanf("%d", &p[i]);

     for(int i = ; i <= n; i++) scanf("%d", &d[i]);

     for(int i = ; i <= n; i++) {

         scanf("%d", &f[i]);

         add(f[i], i);

     }

     for(int i = ; i <= n; i++){

         if(!vis[i]){

             top = ;

             getCir(i);

         }

     }

     LL ans = ;

     for(int i = ; i <= cntCir; i++){

         reverse(cir[i].begin(), cir[i].end());

         for(int j = ; j < cir[i].size(); j++){

             dfs(cir[i][j]);

         }

         LL mn = INF;

         G[][] = dp[cir[i][]][];

         G[][] = dp[cir[i][]][];

         for(int j = ; j < cir[i].size(); j++){

             G[j][] = G[j-][] + dp[cir[i][j]][];

             G[j][] = min(G[j-][]+sum[cir[i][j]], dp[cir[i][j]][]+G[j-][]);

         }

         mn = min(mn, G[cir[i].size()-][]);

         G[][] = sum[cir[i][]];

         G[][] = dp[cir[i][]][];

         for(int j = ; j < cir[i].size(); j++){

             G[j][] = G[j-][] + dp[cir[i][j]][];

             G[j][] = min(G[j-][]+sum[cir[i][j]], dp[cir[i][j]][]+G[j-][]);

         }

         mn = min(mn, G[cir[i].size()-][]);

         ans += mn;

     }

     printf("%lld\n", ans);

     return ;

 }

巴特西

牛客多校第二场B discount 基环内向树

最新文章

热门文章