景区路线规划

题面

暴力不难想到,直接莽就可了

注意,dfs不要写全局变量

考试的时候因为这个挂了QAQ

55pts的code就不放了,太丑了

正解应该是dp或者记忆化搜索

然后,我还没改出来QAQ

好吧,改完了

他们说,这个记忆化搜索也是dpQAQ

设\(dp[i][j][0,1]\)分别表示男和女,在到第i个点,剩余体力为j时当前开心度的期望,然后我懒,用了个结构体,只写了一个dfs

dfs一开始的时候,先判断这个状态之前是否到达过,如果之前到达过,直接返回这个值就可以了

然后其他的就跟普通dfs差不多了,直接放代码吧

Code:

#include<cstdio>
#define MAX 101
#define re register
namespace OMA
{
   struct node
   {
     int next;
     int to;
     int w;
   }edge[MAX*MAX];
   struct data
   { double p1,p2; };
   int cnt=1,head[MAX];
   double ans1,ans2;
   double dp[MAX][MAX*7][2];
   int c[MAX],h1[MAX],h2[MAX];
   inline int read()
   {
     int s=0,w=1; char ch=getchar();
     while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }
     while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }
     return s*w;
   }
   inline void add(int u,int v,int w)
   {
     edge[++cnt].next = head[u];
     edge[cnt].to = v;
     edge[cnt].w = w;
     head[u] = cnt;
   }
   inline data dfs(int u,int k)
   {
     if(dp[u][k][0]||dp[u][k][1])
     { return (data){dp[u][k][0],dp[u][k][1]}; }
     data ans;
     ans.p1=h1[u],ans.p2=h2[u];
     int du=0,to[MAX],w[MAX];
     for(re int i=head[u]; i; i=edge[i].next)
     {
       int v=edge[i].to;
       int t=edge[i].w;
       if(k-t-c[v]>=0)
       { to[++du]=v,w[du]=t; }
     }
     if(!du)
     { return ans; }
     for(re int i=1; i<=du; i++)
     {
       data temp=dfs(to[i],k-w[i]-c[to[i]]);
       ans.p1+=temp.p1/du,ans.p2+=temp.p2/du;
     }
     dp[u][k][0]=ans.p1,dp[u][k][1]=ans.p2;
     return ans;
   }
   signed main()
   {
     int n=read(),m=read(),k=read();
     for(re int i=1; i<=n; i++)
     { c[i]=read(),h1[i]=read(),h2[i]=read(); }
     for(re int i=1; i<=m; i++)
     {
       int u=read(),v=read(),w=read();
       add(u,v,w),add(v,u,w);
     }
     for(re int i=1; i<=n; i++)
     {
       data temp=dfs(i,k-c[i]);
       ans1+=(double)temp.p1,ans2+=(double)temp.p2;
     }
     printf("%.5lf %.5lf\n",ans1/n,ans2/n);
     return 0;
   }
}
signed main()
{ return OMA::main(); }
上一篇:三元环问题


下一篇:Linux下如何快速搜索大文件?