时之终末——题解

呃の，考试时整了两小时，一头雾水——然后。。Rating自然 falling down

题目大意：

给出N个数，可从中最多选M个数，获得这几个数的价值

同时有T个龟则：

对于每个长度为L的子序列，有K个特殊位置，若每个在Xi位置的数都被选，会获得额外价值（有正有负）

M≤N≤100，L，K≤16，T≤100000，2s

一打眼，L≤16，考虑压位DP：

显然只有后L个对下一次的决策有影响，那么就定义 f [ i ] [ s ] [ j ] f[i][s][j] f[i][s][j]：目前处理掉前i个，其中后L个的状态为s，已经选了j个的最大值

每次将当前区间L往后移动一位，考虑第i+1个数的取舍：

不取：

取：

再同样将龟则也转成二进制

然后happy地开始？呵呵呵。。

首先，不取真的一扔过去就Ok了？

设选两数，若子序列的1位置被选则-4

显然这个4在“位移”之后已经成为了一个特殊点，然后就GG了。。

所以不取时

f[i+1][s>>1][j]=max(f[i][s][j]+价值)
           

一看，核心时间空间效率O(NM 2 L 2^{L} 2L)，时间卡得过去，空间滚动数组滚一滚也OK

问题来了，价值怎么算？

显然，集合间存在嵌套关系， 2 2 L 2^{2L} 22L显然不行——然后就有了神奇的子集枚举O( 3 L 3^{L} 3L)

int ts=1<<L;
for(int s=0;s<ts;s++)
		for(int t=s;t;t=(t-1)&s) p[s]+=k[t];
           

再接下来就基本可以开始愉快地敲键盘了。。But，还是有好多坑！！！

1、觉的至多选M个就可以边做边刷答案？想想上面那张很。。的图！！！不刷完后续状态的都不是软柿子！！！

2、滚动滚动，多memset

嗯嗯。。

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=103,maxm=53,maxt=(1<<16)+3;
int n,m,L,Q,ans,a[maxn],p[maxt],k[maxt],count[maxt],f[2][maxt][maxm],INF;
char gt(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int read(){
	int ret=0;bool f=0;char ch=gt();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=gt();
	while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=gt();
	return f?-ret:ret;
}
int main(){
	n=read(),m=read(),L=read(),Q=read();
	for(int i=1;i<=n;i++) a[i]=read();
	int ts=1<<L,add=1<<L-1;
	while(Q--){
		int x=read(),y=read(),now=0;
		while(x--) now|=(1<<read()-1);
		k[now]+=y;
	}
	memset(f[L&1],192,sizeof f[L&1]),INF=f[0][0][0];
	for(int s=0;s<ts;s++){
		for(int t=s;t;t=(t-1)&s) p[s]+=k[t];
		int j=0,now=0;
		for(int i=1;i<=L;i++) if(s&(1<<i-1)) now+=a[i],j++;
		f[L&1][s][count[s]=j]=now+p[s];
	}
	for(int i=L;i<n;i++,memset(f[(i+1)&1],192,sizeof f[(i+1)&1]))
	    for(int s=0;s<ts;s++) 
			for(int j=count[s],tj=m<count[s]+i-L?m:count[s]+i-L;j<=tj;j++)if(f[i&1][s][j]!=INF){
				if(f[i&1][s][j]+p[s>>1]>f[(i+1)&1][s>>1][j]) f[(i+1)&1][s>>1][j]=f[i&1][s][j]+p[s>>1];
				if(f[i&1][s][j]+p[(s>>1)|add]+a[i+1]>f[(i+1)&1][(s>>1)|add][j+1]) f[(i+1)&1][(s>>1)|add][j+1]=f[i&1][s][j]+p[(s>>1)|add]+a[i+1];
			}
	for(int s=0;s<ts;s++)
	  for(int j=0;j<=m;j++) if(f[n&1][s][j]>ans) ans=f[n&1][s][j];
	printf("%d\n",ans);
	return 0;
}
           

仔细思考一下，实际上只要记录后L-1个就OK了。。

然后加点可（wei）爱（suo）的常数优化。。

#pragma GCC optimize(6)
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
const int maxn=103,maxm=53,maxt=(1<<16)+3;
int n,m,L,Q,ans,a[maxn],p[maxt],k[maxt],mid[maxt],count[maxt],f[2][maxt>>1][maxm],INF;
char gt(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int read(){
	int ret=0;bool f=0;char ch=gt();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=gt();
	while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=gt();
	return f?-ret:ret;
}
int main(){
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	n=read(),m=read(),L=read(),Q=read();
	for(int i=1;i<=n;i++) a[i]=read();
	int ts=1<<L,add=1<<L-1;
	while(Q--){
		int x=read(),y=read(),now=0;
		while(x--) now|=(1<<read()-1);
		k[now]+=y;
	}
	memset(f[L&1],192,sizeof f[L&1]),INF=f[L&1][0][0];
	for(int s=0;s<ts;s++){
		for(int t=s;t;t=(t-1)&s) p[s]+=k[t];
		int j=0,now=0;mid[s]=s>>1;
		for(int i=1;i<=L;i++) if(s&(1<<i-1)) now+=a[i],j++;
		if(now+p[s]>f[L&1][mid[s]][j]) f[L&1][mid[s]][j]=now+p[s];
		count[s]=j;
	}
	ts>>=1;
	for(int i=L,ni,ni_;i<n;i++,memset(f[(i+1)&1],192,sizeof f[(i+1)&1])){
		ni=i&1,ni_=(i+1)&1;//常数优化 
	    for(int s=0,ss,ss_,ss__;s<ts;s++){
	    	ss=mid[s],ss_=s|add,ss__=mid[ss_];//常数优化 
			for(int j=count[s],tj=m<count[s]+i-L+1?m:count[s]+i-L+1;j<=tj;j++)if(f[i&1][s][j]!=INF){
				if(f[ni][s][j]+p[s]>f[ni_][ss][j]) f[ni_][ss][j]=f[ni][s][j]+p[s];
				if(f[ni][s][j]+p[ss_]+a[i+1]>f[ni_][ss__][j+1]) f[ni_][ss__][j+1]=f[ni][s][j]+p[ss_]+a[i+1];
			}
	    }
    }
	for(int s=0,ti=n&1;s<ts;s++)
	  for(int j=0;j<=m;j++) if(f[ti][s][j]>ans) ans=f[ti][s][j];
	printf("%d\n",ans);
	return 0;
}