题解 P1850 【换教室】

FREEH · 2018-07-19 22:07:53 · 题解

【题目】

【声明】

• f[i][j][0/1]表示前i个时间点，共申请了j次，第i个时间点否/是进行了申请。

• dis[a][b]表示a教室->b教室的距离

• c[i]表示默认的教室

• d[i]表示更换后的教室

• k[i]表示第i个教室申请成功的概率

【解题思路】

• 本题的分类讨论主要分成两大类，4小类，最后分成9个小项进行考虑。

• 一、当前教室没有申请

  • 如果前一教室有申请： f[i][j][0]=min(f[i-1][j][1]

    • （1）成功：+k[i-1]*dis[d[i-1]][c[i]]
    • （2）失败：+(1-k[i-1])*dis[c[i-1]][c[i]]
  • 如果前一教室没有申请：,f[i-1][j][0],一定是前后均失败：+dis[c[i-1]][c[i]])

• 二、当前教室有申请
  • 如果前一教室有申请：f[i][j][1]=min(f[i-1][j-1][1]
    • （1）前后均成功：+k[i-1]*k[i]*dis[d[i-1]][d[i]]
    • （2）前成功、后失败：+k[i-1]*(1-k[i])*dis[d[i-1]][c[i]]
    • （3）前失败、后成功：+(1-k[i-1])*k[i]*dis[c[i-1]][d[i]]
    • （4）前后均失败：+(1-k[i-1])*(1-k[i])*dis[c[i-1]][c[i]]
  • 如果前一教室没有申请：,f[i-1][j-1][0]
    • （1）后成功：+k[i]*dis[c[i-1]][d[i]]
    • （2）后失败：+(1-k[i])*dis[c[i-1]][c[i]])
• 总结出来的动态转移方程式是：

    f[i][j][0]= min(f[i-1][j][1]+ k[i-1]*dis[d[i-1]][c[i]]+ (1-k[i-1])*dis[c[i-1]][c[i]] ,
f[i-1][j][0] +dis[c[i-1]][c[i]]);

    f[i][j][1]=min(f[i-1][j-1][1]+k[i-1]*k[i]*dis[d[i-1]][d[i]]+k[i-1]*(1-k[i])*dis[d[i-1]][c[i]]+(1-k[i-1])*k[i]*dis[c[i-1]][d[i]]+(1-k[i-1])*(1-k[i])*dis[c[i-1]][c[i]] ,  
f[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1-k[i])*dis[c[i-1]][c[i]])

【解题反思】

• 做这题的时候发现推出来的公式很优秀，程序的Floyd和DP部分也很优秀，但是却总是错样例。结果发现是Floyd初始化的时候把x->x也赋值为了无穷大，gg。毕竟我很久没用Floyd，细节大半都忘记了……这题当做算是回忆起来一些细节了吧！

【参考程序】

#include<cstdio>
#include<iostream>
using namespace std;
const int INF=800000000;
int n,m,v,e;
int c[2005],d[2005],dis[305][305];
double k[2005],f[2005][2005][2];
void Read()
{
    scanf("%d%d%d%d",&n,&m,&v,&e);
    for (int i=1;i<=n;i++)
        scanf("%d",&c[i]);
    for (int i=1;i<=n;i++)
        scanf("%d",&d[i]);
    for (int i=1;i<=n;i++)
        scanf("%lf",&k[i]);
    for (int i=1;i<=v;i++)
        for (int j=1;j<i;j++)
            dis[j][i]=dis[i][j]=INF;
    for (int i=1;i<=e;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        dis[a][b]=min(dis[a][b],w);
        dis[b][a]=dis[a][b];
    }
}

void Floyd()
{
    for (int k=1;k<=v;k++)
        for (int i=1;i<=v;i++)
            for (int j=1;j<i;j++)
                if (dis[i][j]>dis[i][k]+dis[k][j])
                    dis[j][i]=dis[i][j]=dis[i][k]+dis[k][j];
}

void DP()
{
    for (int i=1;i<=n;i++)
        for (int j=0;j<=m;j++)
        {
            f[i][j][0]=f[i][j][1]=INF;
        }
    f[1][0][0]=0;
    f[1][1][1]=0;
    for (int i=2;i<=n;i++)
        for (int j=0;j<=m;j++)
        {
            f[i][j][0]= min(f[i-1][j][1]+ k[i-1]*dis[d[i-1]][c[i]]+ (1-k[i-1])*dis[c[i-1]][c[i]], 
                            f[i-1][j][0] +dis[c[i-1]][c[i]]);
            if (j!=0)
                f[i][j][1]=min(f[i-1][j-1][1]+k[i-1]*k[i]*dis[d[i-1]][d[i]]+k[i-1]*(1-k[i])*dis[d[i-1]][c[i]]+(1-k[i-1])*k[i]*dis[c[i-1]][d[i]]+(1-k[i-1])*(1-k[i])*dis[c[i-1]][c[i]],
                            f[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1-k[i])*dis[c[i-1]][c[i]]);
        }
}

void Write()
{
    double ans=INF;
    for (int i=0;i<=m;i++)
        for (int j=0;j<=1;j++)
        {
            ans=min(ans,f[n][i][j]);
        }
    printf("%.2lf",ans);
}
int main()
{
    Read();
    Floyd();
    DP();
    Write();
    return 0;
}