题意：
你经营者一直棒球队。在接下来的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