【UVA1379】Pitcher Rotation （贪心+DP）

时间：2021-06-12 21:57:28

题意：

　　你经营者一直棒球队。在接下来的g+10天中有g(3<=g<=200)场比赛，其中每天最多一场比赛。你已经分析出你的n(5<=n<=100)个投手中每个人对阵所有m个对手的胜率(一个n*m矩阵)，要求给出作战计划（即每天使用哪个投手），使得总胜场数的期望值最大。注意，一个投手在上场一次后至少要休息4天。

分析：

　　如果这题直接记录前4天中每天上场的投手编号1~n，时间和空间都无法承受。但是，不记录又不行。因为规定一个投手在上场一次后至少要休息4天，也就是说记录前4天的作战计划是必要的，但是我们可以简化这个编号的范围。在这里用到了贪心的思想，对于第i天，我们只会选择当天能力值前5的投手出战。所以记录的时候，只需记录你选的是当天排名第几的投手，然后判断选择不同于前4天的投手DP即可。

　　感觉自己的贪心还是不够好啊~~

代码如下：（好多维，有点恶心，听说不用滚动会疯狂RE，然后我就滚动了。但还是不造为啥依然RE了好多遍TAT）

 #include<cstdio>

 #include<algorithm>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 using namespace std;

 #define Maxn 110

 #define Maxm 40

 #define Maxg 250

 #define Maxd 6

 int p[Maxg][Maxg],d[Maxg];

 int f[][Maxd][Maxd][Maxd][Maxd];

 int b[Maxg][Maxg];

 int n,m,g;

 struct node

 {

     int id,x;

 }t[Maxg];

 bool cmp(node x,node y) {return x.x>y.x;}

 int mymax(int x,int y) {return x>y?x:y;}

 void init()

 {

     scanf("%d%d%d",&n,&m,&g);

     for(int i=;i<=m;i++)

       for(int j=;j<=n;j++)

         scanf("%d",&p[i][j]);

     for(int i=;i<=g+;i++) scanf("%d",&d[i]);

     memset(b,,sizeof(b));

     for(int i=;i<=m;i++)

     {

         for(int j=;j<=n;j++) t[j].id=j,t[j].x=p[i][j];

         sort(t+,t++n,cmp);

         for(int j=;j<=;j++) b[i][j]=t[j].id;

     }

 }

 void dp()

 {

     memset(f,-,sizeof(f));

     f[][][][][]=;

     int np=,ans=;

     int wj=-,wk=-,wl=-,wq=-;

      for(int i=;i<=g+;i++)

      {

        if(d[i]==) continue;

        ans=;

        memset(f[-np],-,sizeof(f[-np]));

        for(int j=;j<=;j++)

         for(int k=;k<=;k++)

          for(int l=;l<=;l++)

           for(int q=;q<=;q++) if(f[np][j][k][l][q]!=-)

           {

               for(int id=;id<=;id++)

               {

                   int now=d[i];

                   if((i-wj<=&&b[now][id]==b[d[wj]][j])||(i-wk<=&&b[now][id]==b[d[wk]][k])||

                     (i-wl<=&&b[now][id]==b[d[wl]][l])||(i-wq<=&&b[now][id]==b[d[wq]][q]))  continue;

                   f[-np][k][l][q][id]=

                     mymax(f[-np][k][l][q][id],f[np][j][k][l][q]+p[now][b[now][id]]);

                   ans=mymax(ans,f[-np][k][l][q][id]);

               }

          }

         wj=wk;wk=wl;wl=wq;wq=i;

         np=-np;

      }

     printf("%.2lf\n",ans*1.0/);

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         init();

         dp();

     }

     return ;

 }

uva1379

2016-03-06 15:42:06

相关文章