UVa

Luogu

分析

首先可以发现,对于一个对手,派去打他的只可能是胜率前五的人中的一个,因为每个人五天可以上场一次。

设 $dp_{i,j,k,l,p}$ 表示前 $i$ 天,第 $i$ 、$i-1$ 、$i-2$ 、$i-3$ 天分别派 $j,k,l,p$ 的最大胜率。

转移枚举一下这一天选谁就好了。注意可能没有对手,转移不太一样。

具体实现及细节见代码。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
#define clean(x,y) memset(x,y,sizeof(x))
using namespace std;

template<typename T>
inline void chkmax(T& x,T y) { if (y>x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10,G=210+10;

int n,m,g;
int a[N][N],d[G];
pair<int,int> b[N];
vector<int> vec[N];
int dp[2][5][5][5][5];

int main() {
    int T=read();
    while (T--) {
        n=read(),m=read(),g=read();
        for (re int i=0;i<=n;++i) vec[i].clear();
        vec[0].push_back(0);
        for (re int i=1;i<=m;++i) {
            for (re int j=1;j<=n;++j) {
                a[i][j]=read();
                b[j]=make_pair(a[i][j],j);
            }
            sort(b+1,b+n+1);
            for (re int j=n;j>n-5;--j)
                vec[i].push_back(b[j].second);
        }
        for (re int i=1;i<=g+10;++i) d[i]=read();
        clean(dp[0],0xc0),dp[0][0][0][0][0]=0;
        for (re int i=1;i<=g+10;++i) {
            int now=i&1,pre=now^1; clean(dp[now],0xc0);
            int pa=i>1?d[i-1]:0,pb=i>2?d[i-2]:0;
            int pc=i>3?d[i-3]:0,pd=i>4?d[i-4]:0;
            if (d[i]) {
                for (re int j=0;j<vec[d[i]].size();++j)
                    for (re int k=0;k<vec[pa].size();++k) {
                        if (vec[d[i]][j]==vec[pa][k]) continue;
                        for (re int l=0;l<vec[pb].size();++l) {
                            if (vec[d[i]][j]==vec[pb][l]) continue;
                            for (re int p=0;p<vec[pc].size();++p) {
                                if (vec[d[i]][j]==vec[pc][p]) continue;
                                for (re int q=0;q<vec[pd].size();++q) {
                                    if (vec[d[i]][j]==vec[pd][q]) continue;
                                    if (dp[pre][k][l][p][q]<0) continue;
                                    chkmax(dp[now][j][k][l][p],dp[pre][k][l][p][q]+a[d[i]][vec[d[i]][j]]);
                                }
                            }
                        }
                    }
            } else {
                for (re int j=0;j<5;++j)
                    for (re int k=0;k<5;++k)
                        for (re int l=0;l<5;++l)
                            for (re int p=0;p<5;++p)
                                chkmax(dp[now][0][j][k][l],dp[pre][j][k][l][p]);
            }
        }
        int ans=0;
        for (re int i=0;i<5;++i)
            for (re int j=0;j<5;++j)
                for (re int k=0;k<5;++k)
                    for (re int l=0;l<5;++l)
                        chkmax(ans,dp[n&1][i][j][k][l]);
        printf("%.2lf\n",ans/100.0);
    }
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 46 PM