dp求调
查看原帖
dp求调
490978
小超手123楼主2022/12/11 21:03

不用看转移,转移我和题解对了的,帮我看看细节有没有写错,如初始化

#include<bits/stdc++.h>
using namespace std;
int n,m,v,e; 
int c[2010],d[2010];
double k[2010];
int f[310][310]; //floyd
double dp[2010][2010][2],ans=1e9;
double min(double a,double b){
	if(a<=b)return a;
	else return b;
}
int main(){
	cin>>n>>m>>v>>e;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++)cin>>d[i];
	for(int i=1;i<=n;i++)cin>>k[i];
	for(int i=1;i<=v;i++)
	    for(int j=1;j<=v;j++)
	        f[i][j]=1e9;
	for(int i=1;i<=e;i++){
		int U,V,W;
		cin>>U>>V>>W;
		f[U][V]=W;
		f[V][U]=W;
	}
	for(int k=1;k<=v;k++)
	    for(int i=1;i<=v;i++)
	        for(int j=1;j<=v;j++)
	            f[i][j]=min(f[i][j],f[i][k]+f[k][i]);
	for(int i=1;i<=v;i++)
	    f[i][i]=0;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
	        dp[i][j][1]=dp[i][j][0]=1e9;
    dp[1][0][0]=dp[1][1][1]=0;
	for(int i=2;i<=n;i++){
		dp[i][0][0]=dp[i-1][0][0]+f[c[i-1]][c[i]];
		for(int j=1;j<=m;j++){
			
			dp[i][j][0]=min(
			dp[i-1][j][0]+f[c[i-1]][c[i]], //i-1不变 
			dp[i-1][j][1]+f[d[i-1]][c[i]]*k[i-1]+f[c[i-1]][c[i]]*(1-k[i-1]));  //i-1变 
			//i不变  
			dp[i][j][1]=min(
			dp[i-1][j-1][0]+f[c[i-1]][d[i]]*k[i]+f[c[i-1]][c[i]]*(1-k[i]), //i-1不变 
			dp[i-1][j-1][1]+f[d[i-1]][d[i]]*k[i]*k[i-1]+f[d[i-1]][c[i]]*k[i-1]*(1-k[i])+f[c[i-1]][d[i]]*(1-k[i-1])*k[i]+f[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])//i-1变 
			);
		}
	}
	for(int i=0;i<=m;i++)
	    ans=min(ans,min(dp[n][i][1],dp[n][i][0]));
	printf("%.2lf",ans);
	return 0;
}
2022/12/11 21:03
加载中...