noip2016 Day1T3

理解错题意了....导致考场上直接爆零TAT

正解就是期望dp啊,dp[i][j][0/1]表示前i节课用了j次机会,这一次用没用的期望代价

看代码吧

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int Mx=310;
int n,m,d,v,C[2010],D[2010];
double dp[2010][2010][2],map[Mx][Mx];
double p[2010],ans=100000007;
int main()
{
  scanf("%d%d%d%d",&n,&m,&d,&v);
  for(int i=0;i<Mx;i++) for(int j=0;j<Mx;j++) map[i][j]=1073741823;
  for(int i=0;i<Mx;i++) map[i][i]=0;
  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++) cin>>p[i];
  for(int i=1;i<=v;i++)
  {
    int x,y;double z;scanf("%d%d%lf",&x,&y,&z);
    map[x][y]=min(map[x][y],z);
    map[y][x]=min(map[y][x],z);
  }
  for(int k=1;k<=d;k++)
    for(int i=1;i<=d;i++)
      for(int j=1;j<=d;j++)
        map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
  for(int i=0;i<2010;i++) for(int j=0;j<2010;j++) dp[i][j][0]=1073741823,dp[i][j][1]=1073741823;
  dp[0][0][0]=0;dp[1][0][0]=0;dp[1][1][1]=0;
  for(int i=2;i<=n;i++) dp[i][0][0]=dp[i-1][0][0]+map[C[i-1]][C[i]];
  for(int i=2;i<=n;i++) for(int j=1;j<=i&&j<=m;j++)

  {
    /*这一位不翻*/dp[i][j][0]=min(dp[i-1][j][0]+map[C[i-1]][C[i]]/*上一位不翻*/,
                     ((dp[i-1][j][1]+map[D[i-1]][C[i]])*p[i-1])+((dp[i-1][j][1]+map[C[i-1]][C[i]])*(1-p[i-1]))/*上一位翻转*/);
    /*这一位翻转*/dp[i][j][1]=min(/*上一位翻转*/

                  ((((dp[i-1][j-1][1]+map[D[i-1]][D[i]])*p[i-1])+((dp[i-1][j-1][1]+map[C[i-1]][D[i]])*(1-p[i-1])))*p[i])//这一位翻转成功
                  +((((dp[i-1][j-1][1]+map[D[i-1]][C[i]])*p[i-1])+((dp[i-1][j-1][1]+map[C[i-1]][C[i]])*(1-p[i-1])))*(1-p[i])),//这一位翻转失败,
              /*上一位不翻*/((dp[i-1][j-1][0]+map[C[i-1]][D[i]])*p[i])+((dp[i-1][j-1][0]+map[C[i-1]][C[i]])*(1-p[i])));
  }
  for(int i=0;i<=m;i++) ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
  printf("%.2lf",ans);
  return 0;
}

上一篇:PTA week10


下一篇:20155303 2016-2017-2 《Java程序设计》第五周学习总结