danihao123's Blog

给定一个\(2n\)张卡的卡组，其中有\(n\)张强化卡（其权值为一大于\(1\)的整数），\(n\)张攻击卡（其权值为一正整数）。在一次游戏中，你需要有序的打出一些卡牌，如果说你打了一张权值为\(x\)的攻击卡，那么对对方造成\(x\)点伤害；如果说你打出了一张权值为\(x\)的强化卡，那么之后所有伤害乘上\(x\)。

现在，你需要随机从卡组中抽出\(m\)张牌，然后选出其中的\(k\)张照一定顺序打出，要求使得产生的伤害最大化。求伤害的期望，答案乘\(\binom{2n}{m}\)再膜\(998244353\)输出。

\(1\leq k\leq m\leq 2n\leq 3000, 1\leq x\leq 10^8\)（其中\(x\)为牌的权值）。

多组数据，满足\(\sum 2n\leq 30000\)。

这个名字真有童话风味哎……

直接LCS肯定会TLE。注意每个序列都是不重复序列，所以可以将A映射到[tex][1,p+1][/tex]，然后再把B映射一下（有的可能A里面没有？反正既然A里没有就和LCS没关系了），就相当于求B的LIS。LIS可以在[tex]O(nlogn)[/tex]时间内完成。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=62510;
#define CL_ARR(x,v) memset(x,v,sizeof(x))

int B[maxn];
int Hash[maxn];
int d[maxn],g[maxn];
int main(){
    int T,n,p,q,x;
    register int i,ans,k,Case=0;
    scanf("%d",&T);
    while(T--){
        Case++;
        scanf("%d%d%d",&n,&p,&q);
        CL_ARR(Hash,0);
        for(i=1;i<=(p+1);i++){
            scanf("%d",&x);
            Hash[x]=i;
        }
        for(i=1;i<=(q+1);i++){
            scanf("%d",&x);
            B[i]=Hash[x];
        }
        CL_ARR(g,0x7f);
        ans=0;
        for(i=1;i<=(q+1);i++){
            k=lower_bound(g+1,g+2+q,B[i])-g;
            d[i]=k;
            g[k]=B[i];
            ans=max(ans,d[i]);
        }
        printf("Case %d: %d\n",Case,ans);
    }
    return 0;
}

第一问很显然是最长不升子序列，直接DP即可。

第二问咋整？暴力？网络流？

其实就是最长不降子序列。具体证明嘛……自己找吧。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=22;
int d[maxn],f[maxn];
int A[maxn];
int main(){
    int n;
    register int i,j,ans=0;
    for(n=1;;n++)
        if(scanf("%d",&A[n])!=1)
            break;
    n--;
    for(i=1;i<=n;i++){
        d[i]=1;
        for(j=i-1;j>=1;j--)
            if(A[j]>=A[i])
                d[i]=max(d[i],d[j]+1);
        ans=max(ans,d[i]);
    }
    printf("%d\n",ans);
    ans=0;
    for(i=1;i<=n;i++){
        f[i]=1;
        for(j=i-1;j>=1;j--)
            if(A[j]<=A[i])
                f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]);
    }
    printf("%d\n",ans);
    return 0;
}