Luogu - changing classrooms - (probability expectation +dp)

P1850

The question ：
It's for you. n lesson , Each class just begins in va[i] classroom , Then you can apply for exchange in every class , Swap to vb[i] classroom , The probability of successful application is f[i]. Then give you the distance between each classroom , And the maximum number of applications in total m. Then we must have classes in order , And then ask you after n lesson , What is the minimum expected value of the journey .

reflection ：
Actually, it's the first time to do this , Think carefully . First of all, I want to ask you the expectation of your journey , Then it's definitely not easy to ask directly for the total . You can separate many paragraphs to ask , about 2 To n, Every time from i-1 Go to the i, Expect once for every such journey , Add up these expectations . For having n lesson ,m Applications , Obviously the , Definition dp[i][j][0/1] by , Up to No i lesson , It was used j Applications , Currently apply or not apply , Minimum expected sum . So when you transfer , Just sort things out . Because the expected value is the sum of all probabilities , So when transferring , If from dp[i-1][j-1][1] To transfer , Let's see how much expectation we need to add , This expectation is the sum of several different situations . Then transfer . This problem can be defined, just used j Applications , You can also define no more than j Time . But there are some differences in the initialization of the two .

Code ：

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e9;
const int N = 2e5+10,M = 2010;

int T,n,m;
int va[M];
int vb[M];
db f[M];
db dist[M][M];
db dp[M][M][2];

signed main()
{
    
	IOS;
	int v,e;
	cin>>n>>m>>v>>e;
	for(int i=1;i<=n;i++) cin>>va[i];
	for(int i=1;i<=n;i++) cin>>vb[i];
	for(int i=1;i<=n;i++) cin>>f[i];
	for(int i=1;i<=v;i++)
	{
    
		for(int j=1;j<=v;j++)
		if(i!=j) dist[i][j] = inf;
	}
	while(e--)
	{
    
		int a,b,c;
		cin>>a>>b>>c;
		dist[b][a] = dist[a][b] = min(dist[a][b],(db)c);
	}
	for(int k=1;k<=v;k++) // First, find the minimum distance between any two points 
	{
    
		for(int i=1;i<=v;i++)
		{
    
			for(int j=1;j<=v;j++)
			dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
		}
	}
	for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j][0] = dp[i][j][1] = inf; // The definition is just right j Time 
	dp[1][0][0] = dp[1][1][1] = 0; // Initialize boundary 
	for(int i=2;i<=n;i++)
	{
    
		for(int j=0;j<=m;j++)
		{
    
			db sum1 = dp[i-1][j][1],sum2 = dp[i-1][j][0]; // It can be transferred from these two types 
			sum1 += f[i-1]*dist[vb[i-1]][va[i]]; 
			sum1 += (1-f[i-1])*dist[va[i-1]][va[i]]; // This type will add the probability expectation of all cases 
			sum2 += dist[va[i-1]][va[i]];
			dp[i][j][0] = min(sum1,sum2); // Take the smallest 
			if(j<1) continue;
			sum1 = dp[i-1][j-1][1],sum2 = dp[i-1][j-1][0]; // In the same way 
			sum1 += f[i-1]*f[i]*dist[vb[i-1]][vb[i]];
			sum1 += (1-f[i-1])*f[i]*dist[va[i-1]][vb[i]];
			sum1 += f[i-1]*(1-f[i])*dist[vb[i-1]][va[i]];
			sum1 += (1-f[i-1])*(1-f[i])*dist[va[i-1]][va[i]];
			sum2 += f[i]*dist[va[i-1]][vb[i]];
			sum2 += (1-f[i])*dist[va[i-1]][va[i]];
			dp[i][j][1] = min(sum1,sum2);
		}
	}
	db anw = inf;
	for(int i=0;i<=m;i++) anw = min(anw,min(dp[n][i][0],dp[n][i][1]));
	printf("%.2lf",anw);
	return 0;
}

summary ：
Think more .