Description
给出一个长度为n(n<=1000)的正整数序列,求一个子序列,使得原序列中任意长度为m的子串中被选出的元素不超过k(k<=m<=10)个,并且选出的元素之和最大。
Input
第一行三个数n,m,k。 第二行n个数,表示各元素数值大小。
Output
一个数,表示最大元素和。
Range
对于10%的数据,n<=10
对于30%的数据,n<=100
对于100%的数据,n<=1000, m从1到10随机(10的情况比较多)
Solution
看范围大概可以想到状压,这题是把m压缩一下。我们首先要预处理一下从0到2m里每个数里有多少个1,这样方便以后的判断。f[i][j]表示以i结尾能取到的最大值,其中j是一个m位二进制数。那么转移方程就很好写了
)|(<<m-)]<=k) f[i+][(j>>)|(<<m-)]=max(f[i+][(j>>)|(<<m-)],f[i][j]+val[i+]); f[i+][j>>]=max(f[i+][j>>],f[i][j]);
这里的状态是反着存的,也就是说:第0位表示i向前第m个数,第1位表示向前m-1个数...第m位表示第i个数。
Code
#include<cstdio> #include<cstring> #include<iostream> #define int long long using namespace std; int n,m,k,maxn; ]; <<]; ][<<]; signed main(){ freopen("best.in","r",stdin); freopen("best.out","w",stdout); scanf(<<m; ;i<=n;i++) scanf("%lld",&val[i]); ;i<maxn;i++) cnt[i]=cnt[i>>]+(i&); memset(f,0xcf,sizeof f); f[][]=; ;i<n;i++){ ;j<maxn;j++){ ) continue; )|(<<m-)]<=k) f[i+][(j>>)|(<<m-)]=max(f[i+][(j>>)|(<<m-)],f[i][j]+val[i+]); f[i+][j>>]=max(f[i+][j>>],f[i][j]); } } ; ;i<maxn;i++) ans=max(ans,f[n][i]); printf("%lld",ans); ; }