月度归档： 2018年10月

这一题的题面很复杂，但形式化地概括则很简单：

对于一个长度为n的全排列，求出其中有多少排列A满足，对于任意i属于n，$$(A_{i}-A{i-1})*(A_{i}-A_{i+1})>=0;$$

然后我们观察排列的特点，我们可以发现，对于排列A中的一个元素\(A_{i}\)，我们可以发现，如果\(A_{i}\)是山峰，那么将\(A_{i}\)的值无论添加多少，都不改变这个序列的可居住性；对于山谷，则反之。
于是，我们可以发现，一个合法的排列，如果我们要在它末尾添上一个数让它形成一个新的合法排列，对于除了最后一个数以及这个数是属于山峰以及山谷以外，我们不关心其他的属性。
因此我们可以用\(f[i][j][k]\)表达当前长度为i，最后一个数为j，最后一个数的状态为k的时候的状态数。其中k==0表示山谷，而k==1表示山峰。
则很容易可以得到状态转移方程：
$$f[i][j][k]+=f[i-1][l][k\ xor\ 1](k?(0<l<=j-1):(j-1<l<=i))$$
但是这样子的复杂度是N^3的，对于4200的数据显然是不能通过的。这时候考虑优化。
我们发现求和的东西是一段区间，因此我们可以考虑前缀优化。
这样子就将复杂度从\(n^3\)降低到了\(n^2\)，于是可以通过。
但是这样子需要的空间是3E7的，对于128MB的空间是非常危险的，这时候考虑滚动数组优化，这样是可以通过的。

#include<iostream>
#include<cstdio>
using namespace std;
long long n,p,f[4205][2],pre[4205][2];
void init(){
    scanf("%lld%lld",&n,&p);
    int l,r;
    f[1][1]=f[1][0]=pre[1][0]=pre[1][1]=1;
    for(int i=2;i<=n;++i){
        pre[i][0]=pre[i-1][0],pre[i][1]=pre[i-1][1];
        for(int j=1;j<=i;++j){
            for(int k=0;k<=1;++k){
                l=k?0:j-1;
                r=k?j-1:i;
                f[j][k]=(pre[r][k^1]-pre[l][k^1]+p)%p;
//                printf("(%d,%d)[%d,%d]%lld|",l,r,pre[l][k^1],pre[r][k^1],f[j][k]);
            }
//            printf(" ");
        }
        pre[0][0]=pre[0][1]=0;
        for(int j=1;j<=i;++j){
            pre[j][0]=(pre[j-1][0]+f[j][0])%p;
            pre[j][1]=(pre[j-1][1]+f[j][1])%p;
        }
//        puts("");
    }
    long long ans=(pre[n][0]+pre[n][1])%p;
    printf("%lld",ans);
}
int main(){
    init();
    return 0;
}

 

Q：为什么这个方程不会重复统计呢？
如果只关心上一个元素的大小，排列中的元素可能重复出现了。

A：不会重复统计，感性证明如下：

首先我们假定对于上一个A，使得：

$$ |A|==i-1 $$

并没有重复统计。
那么我们插入一个新的元素\(i\)时，产生的新序列必然是 本质不同 的。
我们对于\(A_{i-1}\)是山峰和山谷分别讨论。
如果\(A_{i-1}\)是山峰，那么新插入的元素，必然比\(A_{i-1}\)小，并且一定是由将序列中大等于【某个小于等于\(A_{i-1}\)的一个数\(l\)】的所有数提升一，然后将新插入的元素定义为\(l\)。
这时候，\(i-1\)位上的数是\(A_{i-1}+1\)，而\(i\)位上的数则是\(l\)。
在这种情况下，最后两位是\(A_{i-1}+1\)与\(l\)。显然对于每一个本来已有的\(A_{i-1}\)，它们在新的序列中都会加且仅加1。
这样，所有新增的组合的最后两位都是 本质不同 的，因此序列本质不同。
对于山谷，情况类同于山峰，同样可以证明不会产生重复的后两位，进而不会产生本质相同的数列。

而对于 $$|A|==1$$ ，结果显然是1，没有重复统计。
从而归纳得出全部都没有重复统计。

看起来是一道很简单的题，但是细节巨多，消耗了我大量的提交次数。如果是比赛我怕不是凉了。

很显然是一道DP题。
很容易可以想到的是暴力枚举，然而这样做的复杂度是O(n^2*n^2k)的，很很很很显然可以发现是不可行的。
观察数据范围，我们可以注意到， m<=2，因此很容易可以想到状压DP。
具体来说，当m==2时，用f[i][j][l]表示，当前处于第i行，第i行的状态为j，已经使用了l个子矩阵时，最大的和。
则状态转移方程是：

f[i][0][l]=Max(Max(f[i-1][0][l],f[i-1][1][l]),Max(f[i-1][2][l],f[i-1][3][l]));
f[i][1][l]=Max(Max(f[i-1][0][l-1],f[i-1][1][l]),Max(f[i-1][2][l-1],f[i-1][3][l]))+b[i];
f[i][2][l]=Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l],f[i-1][3][l]))+a[i];
f[i][3][l]=Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l]))+a[i]+b[i];

并且我们很容易可以得到边界条件，即：

f[1][0][0]=0,f[1][1][1]=b[1],f[1][2][1]=a[1],f[1][3][1]=a[1]+b[1];

另外需要考虑m==1的情况，事实上这种情况更容易考虑：状态转移方程是：

f[i][0][l]=Max(f[i-1][0][l],f[i-1][1][l]);
f[i][1][l]=Max(f[i-1][0][l-1],f[i-1][1][l])+a[i]; 

初始化f[1][0][0]=0,f[1][1][1]=a[1];

然而交上去全wa
回头考虑这个问题我们可以发现一个很尴尬的事情：当上一行两个取的时候，我们并不知道它到底是「两列分别取」还是「两列一起取」。
因此，对于11的状态，我们应当拆成两个部分：
f[i][3][l]表示上一行的两列是分别取的。于是得到状态转移方程。
f[i][4][l]表示上一行的两列是合在一起取的。

f[i][0][l]=Max(Max(Max(f[i-1][0][l],f[i-1][1][l]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l]);
f[i][1][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-1])+b[i];
f[i][2][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l-1])+a[i];
f[i][3][l]=Max(Max(Max(f[i-1][0][l-2],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-2])+a[i]+b[i];
f[i][4][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l-1])),f[i-1][4][l])+a[i]+b[i];

然而这样子还是全WA。
仔细观察一下我们的状态转移方程，我们发现存在一些l-2的状态，那么我们应该分两类讨论：l==1或l>=2.
这样大概就能通过了。

#include
#include
#include
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
int n,m,k,f[105][5][15],a[105],b[105];

void slv1(){
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    f[1][0][0]=0,f[1][1][1]=a[1];
    for(int i=1;i<=n;++i){
        f[i][0][0]=f[i][1][0]=0;
        for(int l=1;l<=k;++l){
            f[i][0][l]=Max(f[i-1][0][l],f[i-1][1][l]);
            f[i][1][l]=Max(f[i-1][0][l-1],f[i-1][1][l])+a[i]; 
        }
    }
    int ans=-0x3f3f3f3f;
    printf("%d",Max(f[n][0][k],f[n][1][k]));
    return;
}
void slv2(){
    for(int i=1;i<=n;++i){
        scanf("%d%d",&a[i],&b[i]);
    }
    f[0][0][0]=0;
    f[1][0][0]=0,f[1][1][1]=b[1],f[1][2][1]=a[1],f[1][3][2]=a[1]+b[1],f[1][4][1]=a[1]+b[1];
    for(int i=1;i<=n;++i){
        f[i][0][0]=f[i][1][0]=f[i][2][0]=f[i][3][0]=f[i][4][0]=0;
        for(int l=1;l<=k;++l){
                f[i][0][l]=Max(Max(Max(f[i-1][0][l],f[i-1][1][l]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l]);
                f[i][1][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-1])+b[i];
                f[i][2][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l-1])+a[i];
                f[i][4][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l-1])),f[i-1][4][l])+a[i]+b[i];
                if(l<2){
                    continue;
                }
                f[i][3][l]=Max(Max(Max(f[i-1][0][l-2],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-2])+a[i]+b[i];
        }
    }
    /*
    for(int i=1;i<=n;++i){
        for(int l=0;l<=k;++l){
            for(int j=0;j<5;++j){
                printf("%d ",f[i][j][l]);
            }
            puts("");
        }
        puts("");
    }*/
    int ans=-0x3f3f3f3f;
    for(int i=0;i<5;++i){
        ans=Max(ans,f[n][i][k]);
    }
    printf("%d",ans);
}
void init(){
	scanf("%d%d%d",&n,&m,&k);
	memset(f,-1,sizeof(f));
	if(m==1){
	    slv1();
    }
    if(m==2){
        slv2();
    }
}
int main(){
	init();
	return 0;
}