7.20 Codeforces Round #763 (Div. 2) C(二分) D(数学期望）背包+树形dp复习

C. Balanced Stone Heaps

题意：给出n堆石头，然后从第三堆开始从前往后，每堆都可以拿出3x然后给其前放第一堆x个石头，前放第二堆2x个石头。问，堆石头最小个数最大是多少。

最小个数最大，一眼二分。

第一个二分：直接莽上去，只要有大于我给定num值的统统分配。
但是这样发现一个问题，之所以是大于num值才分配，是因为我们不希望产生新的最小值，但是如果这个位置的石头在接受这个位置后方的石头给予后，这堆石头仍然有可能会产生冗余的石头。

我们不妨从后往前进行石头的分配，最后保证了，除了第一第二项外其他所有堆石头必然是符合最小值条件的，然后再检查前两项即可。

#include 

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

D - Robot Cleaner Revisit
题意：n*m的网格里有一堆垃圾和一个机器人，机器人最开始从1，1向右下角移动，碰到障碍后按照相反方向移动，每次移动后（最开始，也就是第0步在初始位置(1,1)不算移动）机器人所在的行列有垃圾时，机器人有p%的概率清扫垃圾。试问机器人清扫走垃圾的期望步数是多少。答案对1e9+7取模。

怎么说呢，数学期望就是情况 * 概率 *步数
这个题每一步，机器人都有清理走垃圾和没有清理走垃圾两种情况。

我们用bi代表第i步清理走垃圾了，用ai代表第i-1步没清理走垃圾

对于步数期望中第i步清理走垃圾就是：i*b[i]

而b[i]=a[i]*p or b[i]=0 （如果机器人所在的行列上没有垃圾，这一步请走垃圾的概率必然是0）
而a[i]应该就是a[i]=a[i-1]*1-p% or a[i]=a[i-1]；（如果这一步所在行列根本就没有垃圾，那么自然100%不会清理走垃圾，那么这一次没清理走垃圾的步数就等于上一步）

好的，基本的三要素初步分析完了之后再来看看这题具体怎么算。

求出步数期望，理当是把第1步，第2步，一直到第正无穷步的所有b[i]*i
根据推理，有如下式子。
下列式子中，t代表第t步。
引用文章：

我个人的分析

#include 
#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;//方向
        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;
}
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

背包复习（恰好装满，变型背包，树上背包）
背包恰好装满情况

背包恰好装满，主要利用了数组初始化设置为一个题目中不可能出现的情况，然后给dp[初始位置下标]=0.然后在后序的正常背包操作中进行判断。

例：
A. Cut Ribbon

#include 
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++)//初始化
        dp[i]=-1;
     //注意dp[0]=0;
    for(int i=1;i<=3;i++)
    {
        for(int j=a[i];j<=n;j++)
        {
            if(dp[j-a[i]]<0)//初始化在这里起的作用
                continue;
            dp[j]=max(dp[j],dp[j-a[i]]+1);
        }
    }
    cout<<dp[n]<<endl;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

这是一道典型的完全背包恰好装满问题。而这是求的最大值。在最小值的时候我们相对应的要把初始化赋值为无穷大。

也就是：正常的背包+恰好装满规则=恰好装满的背包

背包变型，也就是利用背包思想求解的非常规背包问题，这里的价值，容量，花销等通常是推理变型来的。

拓展容量，0-1背包二维变型，不开心的金明
不开心的金明

#include
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

树上背包
P2014 [CTSC1997] 选课
树上背包，实际上是分组背包，发现各个物品之间有依赖关系，所以这是一个在由依赖性构成的树形关系上做分组背包的问题。

背包问题大多是变型背包（但变型并没有特别明显）比如在这道题中，选择m门课程，这个m就和背包的容量有关。

物品：以不同节点为根的子树
状态：以这个节点为根的子树和其内部子树的不同组合。
这样就可以利用分组背包的穷举状态特性来解决。

同样的，作为树形dp的一种，这种题目也大多数是搜到了叶子节点后层层返回

#include 

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--)//背包的容量
        {
            for(int k=0;k<j;k++)//选择的形态
            {
                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;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

树形dp
即：dp+树上dfs
P1352 没有上司的舞会

这种题目的DP[i][j]设计一般是：以i为根的子树，状态j，是什么情况，具体考虑到子节点和父节点列出状态方程。
并且一般是搜到叶子节点后层层返回

#include 

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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

明天：AC自动机学习，字典树、树上差分复习