7.20 codeforces round 763 (Div. 2) C (two points) d (mathematical expectation) Backpack + tree DP review

C. Balanced Stone Heaps

The question ： give n Make stones , Then start from the third pile, from front to back , Each pile can be taken out 3x Then put the first pile in front of it x A stone , Put the second pile in front 2x A stone . ask , What is the minimum and maximum number of stones .

The minimum number is the maximum , One eye and two points .

The first two points ： Go straight up , As long as there is more than I give num Total distribution of values .
But I found a problem like this , The reason is greater than num Value is assigned , It's because we don't want to generate a new minimum , But if the stone in this position is given by the stone behind this position , This pile of stones may still produce redundant stones .

We might as well distribute the stones from the back to the front , Finally, it guarantees , Except for the first and second items, all other heaps of stones must meet the minimum condition , Then check the first two items .

#include <iostream>

#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5+100;
int h[N],n;
int a[N];
int b[N];
bool check(int num)
{
    
    for(int i=1;i<=n;i++)
    {
    
        h[i]=a[i];
        b[i]=0;
    }
    for(int i=n;i>=3;i--)
    {
    
        if(h[i]+b[i]>=num)
        {
    
            int x=(b[i]+h[i]-num)/3;
            x=min(x,h[i]/3);
            b[i-1]+=x;
            b[i-2]+=x*2;
        }
        else
            return 0;
    }
    if(b[1]+h[1]<num)
    {
    
        return 0;
    }
    if(b[2]+h[2]<num)
        return 0;
    return 1;
}
signed main()
{
    
    int t;
    for(cin>>t;t;t--)
    {
    
        cin>>n;
        for(int i=1;i<=n;i++)
        {
    
            cin>>a[i];
        }
        int l=0,r=1e9+1;
        while(l<=r)
        {
    
            int mid=((l+r)/2);
            if(check(mid))
            {
    
                l=mid+1;
            }
            else
            {
    
                r=mid-1;
            }
        }
        cout<<r<<endl;
    }
    return 0;
}

D - Robot Cleaner Revisit
The question ：n*m There is a pile of garbage and a robot in the grid , Robots started from 1,1 Move to the lower right corner , Move in the opposite direction of the camera after encountering obstacles , After every move （ In the beginning , That is the first. 0 Step in the initial position (1,1) Not mobile ） When there is garbage in the ranks of robots , Robots have p% Probability of cleaning garbage . What is the expected number of steps for robots to clean up garbage . The answer is right 1e9+7 modulus .

How to put it? , Mathematical expectation is the situation * probability * They count
Every step of this question , Robots have two situations: cleaning up garbage and not cleaning up garbage .

We use it bi On behalf of the i Step to clean up the garbage , use ai On behalf of the i-1 I didn't clean up the garbage

For the number of steps expected i One step to clean up the garbage is ：i*b[i]

and b[i]=a[i]*p or b[i]=0 （ If there is no garbage on the line of robots , The probability of taking the garbage in this step must be 0）
and a[i] It should be a[i]=a[i-1]*1-p% or a[i]=a[i-1];（ If there is no garbage in this step , It's a natural 100% Won't clean up garbage , Then the number of steps without cleaning up the garbage this time is equal to the previous step ）

well , After the preliminary analysis of the basic three elements, let's see how to calculate this problem .

Find the step number expectation , It should be the first 1 Step , The first 2 Step , All the way to the positive infinite step b[i]*i
According to reason , There is the following formula .
In the following formula ,t On behalf of the t Step .
Quote article ：

My personal analysis

#include <iostream>
#define int long long
#define fastio cout.tie(0);cin.tie(0);ios::sync_with_stdio(0);
using namespace std;
const int N= 4e5+100;
const int mod = 1e9+7;
int n,m,Rx,Ry,rx,ry,p,t;
int a[N],b[N];
int fastpow(int n,int a)
{
    
    int res=1ll;
    while(n)
    {
    
        if(n&1)
            res=res*a%mod;
        n>>=1;
        a=a*a%mod;
    }
    return res%mod;
}
int getinv(int n){
    
    return fastpow(mod-2ll,n);
}
int gcd(int a,int b)
{
    
    return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)
{
    
    return a*b/gcd(a,b);
}
signed main()
{
    
    fastio;
    for(cin>>t;t;t--)
    {
    
        cin>>n>>m>>Rx>>Ry>>rx>>ry>>p;
        int dx=1,dy=1;// Direction 
        int sumb=0,sumbi=0;
        int c=lcm(2*n-2,2*m-2);
        p=p*getinv(100)%mod;
        a[0]=1;
        for(int i=1;i<=c;i++)
        {
    
            if(Rx==rx||Ry==ry)
                a[i]=(a[i-1]*(1ll-p+mod)%mod)%mod;
            else
                a[i]=a[i-1]%mod;
            if(Rx+dx<1||Rx+dx>n) dx*=-1;
            if(Ry+dy<1||Ry+dy>m) dy*=-1;
            Rx+=dx;
            Ry+=dy;
            if(Rx==rx||Ry==ry)
                b[i]=a[i]*p%mod;
            else
                b[i]=0ll;
            sumb=(sumb+b[i])%mod;
            sumbi=(sumbi+b[i]*i%mod)%mod;
        }
        int temp=getinv(( 1ll-a[c]+mod)%mod)%mod;
        int ans1=sumbi*temp%mod;
        int ans2=c*sumb%mod*a[c]%mod*temp%mod*temp%mod;
        cout<<(ans1+ans2)%mod<<endl;
    }
    return 0;
}
 

Backpack review （ It happens to be full of , Variant backpack , Backpack on the tree ）
The backpack is just full

The backpack is just full , The main use of array initialization is set to an impossible situation in a topic , And then to dp[ Initial position subscript ]=0. Then judge in the normal knapsack operation in the following sequence .

example ：
A. Cut Ribbon

#include <bits/stdc++.h>
using namespace std;
int dp[4000+1];
int main()
{
    
	int n,a[4];
	cin>>n;
	for(int i=1;i<=3;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)// initialization 
        dp[i]=-1;
     // Be careful dp[0]=0;
    for(int i=1;i<=3;i++)
    {
    
        for(int j=a[i];j<=n;j++)
        {
    
            if(dp[j-a[i]]<0)// What initialization does here 
                continue;
            dp[j]=max(dp[j],dp[j-a[i]]+1);
        }
    }
    cout<<dp[n]<<endl;
}
}

This is a typical complete backpack that is just full . And this is the maximum value of the solution . At the minimum value, we should correspondingly assign the initialization value to infinity .

That is to say ： Normal backpack + Just full of rules = Just full backpack

Knapsack variant , That is, the unconventional knapsack problem solved by knapsack thought , The value here , Capacity , Expenses, etc. are usually derived from reasoning .

Expand capacity ,0-1 Two dimensional variant of backpack , Unhappy Jin Ming
Unhappy Jin Ming

#include<bits/stdc++.h>
using namespace std;
long long dp[330][110];
long long p[110],v[110];
int main()
{
    
    //freopen("in.txt","r",stdin);
	long long n,w;
	long long minn=1e10,sum=0;
	cin>>n>>w;
	for(int i=1;i<=n;i++)
    {
    
        cin>>v[i]>>p[i];
        minn=minn>v[i]?v[i]:minn;
        sum+=v[i];
    }
    minn--;
    for(int i=1;i<=n;i++)
        v[i]-=minn;
    sum-=n*minn;
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
    
        for(int j=sum;j>=v[i];j--)
        {
    
           for(int k=n;k>=1;k--)
           {
    
               if(j+k*minn<=w)
               dp[j][k]=max(dp[j][k],dp[j-v[i]][k-1]+p[i]);
               ans=max(ans,dp[j][k]);
           }
        }
    }
    cout<<ans<<endl;
	return 0;
}

Backpack on the tree
P2014 [CTSC1997] Course selection
Backpack on the tree , It's actually a group backpack , Find dependencies between items , So this is a problem of grouping knapsacks on tree relationships composed of dependencies .

Backpack problems are mostly variant backpacks （ But the variant is not particularly obvious ） For example, in this question , choice m Courses , This m It's related to the capacity of the backpack .

goods ： Subtree rooted in different nodes
state ： Different combinations of subtrees rooted at this node and its internal subtrees .
In this way, we can solve the problem by using the exhaustive state property of the packet knapsack .

alike , As a tree dp A kind of , Most of these problems are returned layer by layer after finding leaf nodes

#include <iostream>

using namespace std;
const int N = 300+100;
struct node
{
    
    int nex,to;
};
int n,m;
node edge[N<<1];
int head[N],tot;
int w[N];
int dp[N][N];
void add(int from,int to)
{
    
    edge[++tot].to=to;
    edge[tot].nex=head[from];
    head[from]=tot;
}
void DFS(int now)
{
    
    dp[now][1]=w[now];
    for(int i=head[now];i;i=edge[i].nex)
    {
    
        int to=edge[i].to;
        DFS(to);
        for(int j=m+1;j>0;j--)// The capacity of the backpack 
        {
    
            for(int k=0;k<j;k++)// Selected form 
            {
    
                dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[to][k]);
            }
        }
    }
}
int main()
{
    
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    
        int a;
        cin>>a>>w[i];
        add(a,i);
    }
    DFS(0);
    cout<<dp[0][m+1]<<endl;
    return 0;
}

Tree form dp
namely ：dp+ on the tree dfs
P1352 A dance without a boss

This topic is DP[i][j] The design is generally ： With i Root subtree , state j, What's the situation , Specifically, consider that the child node and parent node list the state equation .
And it usually returns layer by layer after finding the leaf node

#include <iostream>

using namespace std;
const int N = 6000+100;
struct node
{
    
    int nex,to;
};
node edge[N<<1];
int rd[N];
int head[N],tot;
int dp[N][2];
void add(int from,int to)
{
    
    edge[++tot].to=to;
    edge[tot].nex=head[from];
    head[from]=tot;
}
void DFS(int now,int fath)
{
    
    for(int i=head[now];i;i=edge[i].nex)
    {
    
        int to=edge[i].to;
        if(edge[i].to==fath)
            continue;
        DFS(edge[i].to,now);
        dp[now][0]=max(dp[now][0],max(dp[now][0]+dp[to][1],max(dp[to][0],dp[to][1])));
        dp[now][1]=max(dp[now][1],max(dp[now][1]+dp[to][0],dp[to][0]));
    }
}
int main()
{
    
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    
        cin>>dp[i][1];
    }
    for(int i=1;i<=n-1;i++)
    {
    
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
        rd[b]++;
    }
    int root;
    for(int i=1;i<=n;i++)
    {
    
        if(rd[i]==0)
        {
    
            root=i;
            break;
        }
    }
    DFS(root,0);
    cout<<max(dp[root][0],dp[root][1])<<endl;
    return 0;
}

Tomorrow, ：AC Automata learning , Dictionary tree 、 Differential review on the tree