P1850 [NOIP2016 提高組] 換教室

題意：

有2n個課安排在n個時間段上，每個時間段上都有兩個一樣的課同時在不同地方上，起初牛牛被所有課都被安排在Ci上課，另一節課在Di上課。牛牛現在想跟換到Di位置，它最多可以申請m節課換教室，對于每節課換成功的概率為P[i],每個教室之間都有距離，問申請哪幾門課程可以使他在教室間的移動總和的期望值最小，輸出這個最小值
注意申請教室是一次性的，無法根據其他課的申請結果來決定其他課程是否申請

題解：

按照一般的思路，我們會設dp[i][j]表示前i個課我們申請了j節，移動的最小期望值。dp[i][j] =min(dp[i-1][j-1]+p[i] * dis +dp[i-1][j]+(1-p[i]) * dis),我們可能會得到這樣的方程，但是有個大問題，因為我們在轉移過程中被認為是知道上一次申請的結果的，但是在題目中，所有申請是一次提交的，我們并不知道上一次申請會是什么樣的結果，所以二維狀態是不夠用的。所以我們設dp[i][j][0/1],前兩維意思相同，第三維表示我們假設第i個教室我們沒有選擇交換(交換是否成功未知，只是我們提交了申請)
那么我們轉移會有考慮當前當前是否轉移，以及上一次是否轉移
轉移情況如圖：

詳細見代碼吧

代碼：

調了半天不知道哪寫錯了，直接找了AC代碼

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std; //Fe~Jozky const ll INF_ll=1e18; const int INF_int=0x3f3f3f3f; inline ll read(){ll s=0,w=1ll;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1ll;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10ll+((ch-'0')*1ll),ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=2030; double dp[maxn][maxn][3]; double dis[maxn][maxn]; int c[maxn],d[maxn]; double p[maxn]; int n,m,v,e; void Floyd(){for(int i=1;i<=v;i++){for(int j=1;j<=v;j++){for(int k=1;k<=v;k++){dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);}}} } void init(){for(int i=1;i<=v;i++){for(int j=1;j<=v;j++){dis[i][j]=1e9;}} } int main() {cin>>n>>m>>v>>e;init();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>>p[i];for(int i=1;i<=e;i++){int u,v,w;cin>>u>>v>>w;dis[u][v]=w;dis[v][u]=w;}Floyd();for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){dp[i][j][0]=dp[i][j][1]=1e9;}}dp[1][0][0]=dp[1][1][1]=0; //初始化 for(int i=2;i<=n;i++){for(int j=0;j<=min(m,i);j++){dp[i][j][0]=min(dp[i-1][j][0]+dis[c[i-1]][c[i]],dp[i-1][j][1]+dis[d[i-1]][c[i]]*p[i-1]+dis[c[i-1]][c[i]]*(1-p[i-1]));if(j!=0)dp[i][j][1]=min(dp[i-1][j-1][0]+dis[c[i-1]][d[i]]*p[i]+dis[c[i-1]][c[i]]*(1-p[i]),dp[i-1][j-1][1]+dis[c[i-1]][c[i]]*(1-p[i-1])*(1-p[i])+dis[c[i-1]][d[i]]*(1-p[i-1])*p[i]+dis[d[i-1]][c[i]]*(1-p[i])*p[i-1]+dis[d[i-1]][d[i]]*p[i-1]*p[i]);}}double Dis=1e9;for(int i=0;i<=m;i++)Dis=min(min(dp[n][i][0],dp[n][i][1]),Dis);printf("%.2f",Dis);return 0; }

AC代碼

#include<iostream> #include<cstdio> using namespace std; double p[10001],f[2001][2001],dp[2001][2001][2]; int a[2001][2001],c[20001],d[20001]; inline double min(double a,double b){return a<b?a:b; } inline int qread(){int k = 0;char c;c = getchar();while(!isdigit(c))c = getchar();while(isdigit(c)){k = (k<<1)+(k<<3)+c-48;c = getchar();}return k ; } int main() {int n,m,v,e,a1,b1,c1;cin>>n>>m>>v>>e;for( int i=1;i<=n;i++)c[i]=qread();for( int i=1;i<=n;i++)d[i]=qread();for( int i=1;i<=n;i++)cin>>p[i];for( int i=1;i<=v;i++)for( int j=1;j<i;j++)f[i][j]=f[j][i]=999999999;for( int i=1;i<=e;i++){a1=qread(),b1=qread(),c1=qread();f[a1][b1]=f[b1][a1]=min(f[a1][b1],c1);}for( int k=1;k<=v;k++)for( int i=1;i<=v;i++)for( int j=1;j<i;j++)if(f[i][k]+f[k][j]<f[i][j])f[i][j]=f[j][i]=f[i][k]+f[k][j];for( int i=1;i<=n;i++)for( int j=0;j<=m;j++)dp[i][j][0]=dp[i][j][1]=999999999;dp[1][0][0]=dp[1][1][1]=0;for( int i=2;i<=n;i++){double add1=f[c[i-1]][c[i]];for( int j=0;j<=min(m,i);j++){ dp[i][j][0]=min(dp[i-1][j][0]+add1,dp[i-1][j][1]+f[d[i-1]][c[i]]*p[i-1]+f[c[i-1]][c[i]]*(1-p[i-1]));if(j!=0)dp[i][j][1]=min(dp[i-1][j-1][0]+f[c[i-1]][d[i]]*p[i]+f[c[i-1]][c[i]]*(1-p[i]),dp[i-1][j-1][1]+f[c[i-1]][c[i]]*(1-p[i-1])*(1-p[i])+f[c[i-1]][d[i]]*(1-p[i-1])*p[i]+f[d[i-1]][c[i]]*(1-p[i])*p[i-1]+f[d[i-1]][d[i]]*p[i-1]*p[i]);} } double hahaha=9999999999;for(int i=0;i<=m;i++){hahaha=min(dp[n][i][0],min(dp[n][i][1],hahaha));}printf("%.2lf",hahaha); }

總結

以上是生活随笔為你收集整理的P1850 [NOIP2016 提高组] 换教室的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。