 /**//*
题意:n个选手,m个对手 给出m*n的表,[i,j]表示用第j个选手赢第i个对手的分
先给出g+10天的日程,每天可能有一场比赛(对手可以重复),可能没有
每个选手用了,至少需要休息4天 问最大的分
一开始我也能想到,用4维记录当天以及之前的3天 但状态数达n^4
问了别人,每场只需要5个最大选手即可!!!因为就算该场前面那4个最大的前4天已选了,还有1个
变为5^4
然后直接5维dp
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;


vector<pair<int,int> >p[105];
int x[220];
int dp[2][5][5][5][5];

bool cmp(const pair<int,int> &A,const pair<int,int> &B)
  {
return A.first>B.first;
}

 inline int max(int a,int b) {return a>b?a:b;}

int main()
  {
//freopen("in","r",stdin);
int T,n,g,m;
for(scanf("%d",&T);T--;)
 {
scanf("%d%d%d",&n,&m,&g);
g+=10;
for(int i=1;i<=m;i++)
 {
p[i].clear();
for(int j=1,val;j<=n;j++)
 {
scanf("%d",&val);
p[i].push_back(make_pair(val,j));
}
sort(p[i].begin(),p[i].end(),cmp);
}
n=min(n,5);
memset(dp,0,sizeof(dp));
int pre=0,now=1;
for(int i=1;i<=g;i++)
 {
scanf("%d",&x[i]);
//remember to check x[i] = 0
for(int a=0;a<n;a++)
for(int b=0;b<n;b++)
 {
if(i>4&&x[i-4]&&x[i-3]&&p[x[i-4]][a].second==p[x[i-3]][b].second)continue;
for(int c=0;c<n;c++)
 {
if(i>3&&x[i-3]&&x[i-2]&&p[x[i-3]][b].second==p[x[i-2]][c].second)continue;
if(i>4&&x[i-4]&&x[i-2]&&p[x[i-4]][a].second==p[x[i-2]][c].second)continue;
for(int d=0;d<n;d++)
 {
if(i>2&&x[i-2]&&x[i-1]&&p[x[i-2]][c].second==p[x[i-1]][d].second)continue;
if(i>3&&x[i-3]&&x[i-1]&&p[x[i-3]][b].second==p[x[i-1]][d].second)continue;
if(i>4&&x[i-4]&&x[i-1]&&p[x[i-4]][a].second==p[x[i-1]][d].second)continue;
for(int e=0;e<n;e++)//
 {
if(i>1&&x[i-1]&&x[i]&&p[x[i-1]][d].second==p[x[i]][e].second)continue;
if(i>2&&x[i-2]&&x[i]&&p[x[i-2]][c].second==p[x[i]][e].second)continue;
if(i>3&&x[i-3]&&x[i]&&p[x[i-3]][b].second==p[x[i]][e].second)continue;
if(i>4&&x[i-4]&&x[i]&&p[x[i-4]][a].second==p[x[i]][e].second)continue;
dp[now][b][c][d][e]=max(dp[now][b][c][d][e],dp[pre][a][b][c][d]+(x[i]?p[x[i]][e].first:0));
}
}
}
}
swap(pre,now);
}
int ans = 0;
for(int a=0;a<n;a++)
for(int b=0;b<n;b++)
for(int c=0;c<n;c++)
for(int d=0;d<n;d++)
ans=max(ans,dp[pre][a][b][c][d]);
printf("%d.%02d\n",ans/100,ans%100);
}

return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|