Description
对于刚上大学的牛牛来说, 他面临的第一个问题是如何根据实际情况中情合适的课程。
在可以选择的课程中,有2n节课程安排在n个时间段上。在第 i ( 1≤ i≤n)个时同段上, 两节内容相同的课程同时在不同的地点进行, 其中, 牛牛预先被安排在教室 ci上课, 而另一节课程在教室 di进行。
在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的n节安排好的课程。如果学生想更换第i节课程的教室,则需要提出中情。若申请通过,学生就可以在第 i个时间段去教室 di上课, 否则仍然在教室 ci上课。
由于更换教室的需求太多, 申请不一定能获得通过。 通过计算, 牛牛发现申请更换第 i节课程的教室时, 中情被通过的概率是一个已知的实数 ki, 并且对于不同课程的申请, 被通过的概率是互相独立的。
学校规定, 所有的申请只能在学期开始前一次性提交, 并且每个人只能选择至多m节课程进行申请。 这意味着牛牛必须一次性决定是否申请更换每节课的教室, 而不能根据某些课程的申请结果来决定其他课程是否申请; 牛牛可以申请白己最希望更换教室的 m门课程,也可以不用完这m个中情的机会,甚至可以一门课程都不申请。
因为不同的课程可能会被安排在不同的教室进行, 所以牛牛需要利用课问时间从一间教室赶到另一间教室。
牛牛所在的大学有 v个教室,有 e条道路。每条道路连接两间教室, 并且是可以双向通行的。 由于道路的长度和拥;i者程度不同, 通过不同的道路耗费的体力可能会有所不同。当第i ( 1≤i≤n-1 )节课结束后,牛牛就会从这节课的教室出发,选择一条耗费体力最少的路径前往下一节课的教室。
现在牛牛想知道,申请哪几门课程可以使他因在教室问移动耗费的体力值的总和的期望值最小,请你帮他求出这个最小值。
显然DP，（神tmDP）。
首先想到，每一节课都有申请和不申请两状态，然后，每次申请成功的概率为k[i]，那么，i申请状态的期望值就是min(上一个申请的期望值+各种起点和终点的概率*距离，上一个不申请的期望值+各种起点和终点的概率*距离)；
不申请同理。
又因为有次数限制，所以二维DP。
dp[0][i][j]表示第i节课，申请窜课，已经用了j次机会的期望值。
得： dp[0][i][j]=min(
dp[0][i-1][j-1]
+lk[i-1]*map[d[i-1]][d[i]]*lk[i]
+(1.0-lk[i-1])*map[c[i-1]][d[i]]*lk[i]
+(1.0-lk[i-1])*map[c[i-1]][c[i]]*(1.0-lk[i])
+lk[i-1]*map[d[i-1]][c[i]]*(1.0-lk[i])
,
dp[1][i-1][j-1]
+map[c[i-1]][d[i]]*lk[i]
+map[c[i-1]][c[i]]*(1.0-lk[i]));
dp[1][i][j]表示不申请窜课的期望值。得：
dp[1][i][j]=min(
dp[0][i-1][j]
+(1-lk[i-1])*map[c[i-1]][c[i]]
+lk[i-1]*map[d[i-1]][c[i]]
,
dp[1][i-1][j]
+map[c[i-1]][c[i]]
);
脱式写的好清真。
第一次写这道题时将申请的情况分两种（成功和不成功）考虑了，最后加和更新答案。虽然DP方程写对了，但是策略不对，局部的最优解加和可能不对，由于一节课只能申请或是不申请，所以不能出现用不申请更新申请成功的期望，再用申请更新申请不成功的期望。所以错误。
dp[0][i][j]=min(dp[0][i-1][j-1]+(1-lk[i-1])*map[c[i-1]][c[i]]+dp[1][i-1][j-1]+lk[i-1]*map[d[i-1]][c[i]]
,dp[2][i-1][j-1]+map[c[i-1]][c[i]])*(1-lk[i]);
dp[1][i][j]=min(dp[0][i-1][j-1]+(1-lk[i-1])*map[c[i-1]][d[i]]+dp[1][i-1][j-1]+lk[i-1]*map[d[i-1]][d[i]]
,dp[2][i-1][j-1]+map[c[i-1]][d[i]])*lk[i];
dp[2][i][j]=min(dp[0][i-1][j]+(1-lk[i-1])*map[c[i-1]][c[i]]+dp[1][i-1][j]+lk[i-1]*map[d[i-1]][c[i]]
,dp[2][i-1][j]+map[c[i-1]][c[i]]);
以后DP要注意局部最优和对答案的更新的关系
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,sum_v,sum_e;
double dp[2][2100][2100],ans,lk[2100];
int map[310][310],c[2100],d[2100];
int read()
{
char ch=getchar();int re=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
int main()
{
n=read();m=read();sum_v=read();sum_e=read();
for(int i=1;i<=n;i++) c[i]=read();
for(int i=1;i<=n;i++) d[i]=read();
for(int i=1;i<=n;i++) scanf("%lf",&lk[i]);
memset(map,0x3f,sizeof(map));
for(int x,y,z,i=1;i<=sum_e;i++)
{
x=read();y=read();z=read();
if(z<map[x][y]) map[x][y]=map[y][x]=z;
}
for(int i=1;i<=sum_v;i++) map[i][i]=0;
for(int k=1;k<=sum_v;k++)
for(int i=1;i<=sum_v;i++)
for(int j=1;j<=sum_v;j++)
if(map[i][j]>map[i][k]+map[k][j])
map[i][j]=map[i][k]+map[k][j];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
dp[1][i][j]=dp[0][i][j]=1047483647.0;
dp[1][1][0]=dp[0][1][1]=0;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=m&&j<=i;j++)
{
if(j>=1)
dp[0][i][j]=
min(
dp[0][i-1][j-1]
+lk[i-1]*map[d[i-1]][d[i]]*lk[i]
+(1.0-lk[i-1])*map[c[i-1]][d[i]]*lk[i]
+(1.0-lk[i-1])*map[c[i-1]][c[i]]*(1.0-lk[i])
+lk[i-1]*map[d[i-1]][c[i]]*(1.0-lk[i])
,
min(
dp[0][i][j]
,
map[c[i-1]][d[i]]*lk[i]
+dp[1][i-1][j-1]
+map[c[i-1]][c[i]]*(1.0-lk[i])
)
);
dp[1][i][j]=
min(
dp[0][i-1][j]
+(1-lk[i-1])*map[c[i-1]][c[i]]
+lk[i-1]*map[d[i-1]][c[i]]
,
min(
dp[1][i][j]
,
dp[1][i-1][j]
+map[c[i-1]][c[i]]
)
);
}
}
ans=1147483647.0;
for(int i=0;i<=m;i++)
ans=min(min(dp[0][n][i],dp[1][n][i]),ans);
printf("%.2lf",ans);
return 0;
}