C++14(g++5.4) 解法, 执行用时: 1348ms, 内存消耗: 29388K, 提交时间: 2019-07-07 20:59:12

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 110
#define M 51
#define S 1<<16
#define inf 0xefefefef
using namespace std;
int n,m,up,l,now=0;
int a[N],f[S],g[2][M][S],s[S];
int main(){
    scanf("%d%d%d%d",&n,&m,&up,&l);
    up=min(up,n);
    for (int i=1;i<=n;i++) 
		scanf("%d",&a[i]);
    for (int i=1;i<=l;i++){
        int x,y,s=0,t,mx=0;
        scanf("%d%d",&x,&y);
        while (x--){
            scanf("%d",&t);
            s^=1<<t-1;
        }
        f[s]+=y;
    }
    memset(g,inf,sizeof g);
    int mx=(1<<up)-1;
    for (int i=0;i<=mx;i++){
    	int t=0,x=i;
    	while (x){
    		t+=x&1;
    		x>>=1;
		}
        int &s=g[now][t][i]=0;
        for (int j=i;j;--j&=i) s+=f[j];
        for (int j=0;j<=up-1;j++) 
			if (i>>j&1) s+=a[j+1];
    }
    memset(s,0xef,sizeof s);
    for (int i=2;i<=n-up+1;i++){
        now^=1;
        memset(g[now],inf,sizeof g[now]);
        for (int j=0;j<=m;j++) 
			for (int k=0;k<=mx;k++) 
				if (g[!now][j][k]!=inf){
            		int &_g=g[!now][j][k];
            		int next=k>>1^1<<up-1;
            		if (s[next]==inf){
                		s[next]=0;
                		for (int x=next;x;--x&=next) 
							s[next]+=f[x];
            		}
            		g[now][j+1][next]=max(g[now][j+1][next],_g+a[i+up-1]+s[next]);
            		next=k>>1;
            		if (s[next]==inf){
            			s[next]=0;
                		for (int x=next;x;--x&=next) 
							s[next]+=f[x];
            		}
            		g[now][j][next]=max(g[now][j][next],_g+s[next]);
        		}
    }
    int ans=0;
    for (int i=0;i<=m;i++) 
		for (int j=0;j<=mx;j++) 
			ans=max(ans,g[now][i][j]);
    printf("%d\n",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 548ms, 内存消耗: 23536K, 提交时间: 2020-08-14 00:38:23

#include<bits/stdc++.h>
using namespace std;
 
int DP[2][55][66000],S[66000]={0},R[105];
int main()
{
    int i,j,k,x,y,n,m,a,b,ans=-2e9;
    scanf("%d%d%d%d",&n,&m,&a,&b);
    for(i=0;i<n;i++)scanf("%d",&R[i]);
    while(b--)
    {
        scanf("%d%d",&x,&y),j=0;
        while(x--)scanf("%d",&i),j|=1<<(i-1);
        S[j]+=y;
    }
    for(i=0;i<a;i++)
        for(j=0;j<(1<<a);j++)if(((1<<i)&j)==0)S[j|1<<i]+=S[j];
    for(j=0;j<=m;j++)
        for(k=0;k<(1<<a);k++)DP[0][j][k]=-2e9;
    for(i=0;i<(1<<a);i++)
    {
        for(j=k=x=0;j<a;j++)if((1<<j)&i)k++,x+=R[j];
        DP[0][k][i]=max(DP[0][k][i],x+S[i]);
    }
    for(x=0,i=a;i<n;i++,x^=1)
    {
        for(j=0;j<=m;j++)
            for(k=0;k<(1<<a);k++)DP[x^1][j][k]=-2e9;
        for(j=0;j<=m;j++)
            for(k=0;k<(1<<a);k++)
            {
                if(DP[x][j][k]==-2e9)continue;
                DP[x^1][j][k>>1]=max(DP[x^1][j][k>>1],DP[x][j][k]+S[k>>1]);
                if(j<m)DP[x^1][j+1][(k>>1)|(1<<(a-1))]=max(DP[x^1][j+1][(k>>1)|(1<<(a-1))],DP[x][j][k]+R[i]+S[(k>>1)|(1<<(a-1))]);
            }
    }
    for(i=0;i<=m;i++)
        for(j=0;j<(1<<a);j++)ans=max(ans,DP[x][i][j]);
    printf("%d\n",ans);
    return 0;
}