/**//* 题意: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
搜索
最新评论
|
|