1540 : 自信心

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

有 n 个学生按照序号从左到右依次排成一排进行考试。这 n 个学生的学习能力两两不同。对于第 i 个学生，如果有 j 个同学比他学习能力差且和他的座位之间最多隔一个位置，那么 i 同学考试时的自信心为 Aij。

但不幸的是，记录学生学习能力的表格丢失了。作为一个悲观的人A老师想请你帮助他计算出最坏情况下学生自信心总和为多少，即最小可能为多少。

输入

第一行一个数 T，表示数据组数
对于每一组数据：
第一行一个数 n
接下来 n 行，每行5个数分别表示 Ai0 ~ Ai4

对于30%的数据，1 ≤ n ≤ 10
对于50%的数据，1 ≤ n ≤ 100
对于100%的数据，1 ≤ T ≤ 10, 1 ≤ n ≤ 100000, 1 ≤ Aij ≤ 10000

输出

对于每组数据输出一个数，表示答案

样例输入

1
3
1 2 3 4 5
2 1 3 4 5
2 3 1 4 5

样例输出

3

分析

首先是生成全排列的方法，可以拿30分，就不说了。

这个题很明显是要DP的，我们可以设前i个学生的最小自信心总和为f[i]，显然第i个人的取值取决于i前两人和后两人相对于他的关系，因此考虑设f[i][j]代表区间[i-2,i+2]五个人的相对排名为j的时候，前i个人的最小总和。其中，j是一个[1,5]的全排列，例如j=(4,1,5,3,2)时，代表第i-2,i-1,i,i+1,i+2人在这五个人之中的相对排名为4,1,5,3,2。
这么做的话，转移的时候就非常方便了，对于任意一个f[i][j]，根据j就可以确定f[i-1][k]中k的后四人的相对排名，而k中第一人的相对排名可以枚举从1到5插入到后四人中。
例如j=(4,1,5,3,2)时，前四人的相对排名是(4,1,5,3)->(3,1,4,2)
即k中后四人的相对排名应该是(3,1,4,2)，那么枚举第一人的排名，可以得到k可能的排列是:
(1,4,2,5,3),(2,4,1,5,3),(3,4,1,5,2),(4,3,1,5,2),(5,3,1,4,2)

同时，根据状态f[i][j]，j的第三位，也就是i的排名，可以直接得到他的自信心的取值为：a[i][5-排名]，所以状态转移方程为：
需要注意的是边界条件（问号处是一个2~5的排列）：
这个很好理解，第0个人不会影响到后面的人的自信心，所以直接假设他的相对排名是第一就好了。同理，最后我们要求的状态便是：

这里需要注意的是关于状态j的存储，由于j是一个1~5的全排列，所以可以根据康托展开直接映射到区间[1，120]上。所以不需要开5维，这个映射可以事先预处理并保存下来。同样可以预处理的是j所有可以用于转移的状态k。容易发现，对于任何一个状态j,能转移到j的状态k都只有5个，没必要每次都去枚举状态，也可以事先预处理并保存。

最后分析一下复杂度，状态量总共是N*5！，转移的复杂度是5，总的复杂度就是N * 600，最坏情况下，由于还有T=10组数据，总的来看可以说是AC得非常惊险，最后运行时间好像是940ms= =。。。

PS：官方题解的状态表示比我的要优秀，复杂度也小很多，不过我没看太懂，就不说了ORZ_

AC代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<string>
#include<stack>
#include<set>
#define mem(f) memset(f,0,sizeof(f))
#define P2 pair<LL,LL>
#define double char
typedef long long LL;
using namespace std;
const LL MOD = 1e9+7;
const int N = 200005;
const int MININT = 0x80000000;
const int MAXINT = 0x3FFFFFFF;
int n,z[N][5],f[N][121];
int facts[]={1,1,2,6,24,120,720};
vector<int> trans[121];
vector<int> lis[121];
void init()
{
    int i;
    cin >> n;
    for(i=1;i<=n;i++)
        scanf("%d%d%d%d%d",&z[i][0],&z[i][1],&z[i][2],&z[i][3],&z[i][4]);
}

vector<int> reverse_kangtuo(int n,int k)
{
    int i, j, t, vst[8]={0};
    vector<int> s;
    --k;
    for (i=0; i<n; i++)
    {
        t = k/facts[n-i-1];
        for (j=1; j<=n; j++)
            if (!vst[j])
            {
                if (t == 0) break;
                --t;
            }
        s.push_back(j);
        vst[j] = 1;
        k %= facts[n-i-1];
    }
    return s;
}

int kangtuo(int n,vector<int> a)
{
    int i,j,t,sum;
    sum=0;
    for( i=0; i<n ;++i)
    {
        t=0;
        for(j=i+1;j<n;++j)
            if( a[i]>a[j] )
                ++t;
        sum+=t*facts[n-i-1];
    }
    return sum+1;
}

void prep()
{
    int i,j,k;
    for(i=1;i<=120;i++)
    {
        vector <int> st1=reverse_kangtuo(5,i);
        lis[i]=st1;
        vector <int> st2(5);
        st2.assign(st1.begin()+1,st1.begin()+5);st2.push_back(0);
        for(j=0;j<4;j++)
            if(st2[j]>st1[0]) st2[j]--;
        vector <int> st3;
        for(k=1;k<=5;k++)
        {
            st3=st2;
            st3[4]=k;
            for(j=0;j<4;j++)
                if(st3[j]>=k) st3[j]++;
            trans[kangtuo(5,st3)].push_back(i);
        }
    }
}

void work()
{
    int i,j,k,ans=MAXINT;
    for(i=0;i<=n;++i)
        for(j=0;j<=120;++j)
            f[i][j]=MAXINT;
    for(j=1;j<=120;j++)
        if(lis[j][3]>3&&lis[j][4]>3)
            f[0][j]=0;
    for(i=1;i<=n;++i)
        for(j=1;j<=120;++j)
            for(k=0;k<5;++k)
            {
                f[i][j]=min(f[i][j],f[i-1][trans[j][k]]+z[i][5-lis[j][2]]);
                if(i==n&&lis[j][3]<3&&lis[j][4]<3)
                    ans=min(ans,f[i][j]);
            }
    cout << ans << endl;
}

int main()
{
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    prep();
    int t;
    scanf("%d\n",&t);
    while(t--)
    //while(cin >> n)
    {
        init();
        work();
    }
    return 0;
}