hiho 1044

// // main.cpp // hiho1044 // // Created by Fangpin on 15/4/28. // Copyright (c) 2015年 FangPin. All rights reserved. // #include <iostream> #include <cstdio> #include <cstring> using namespace std; int n,m,q; int dp[1005][1029],a[1004]; int cnt(int x){ int ans=0; while(x){ if(x&1) ++ans; x>>=1; } return ans; } int main(int argc, const char * argv[]) { // insert code here... // std::cout << "Hello, World! "; // int n,m,q; scanf("%d%d%d",&n,&m,&q); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int i=1;i<=n;++i){ for(int j=0;j<(1<<m);++j){ int s0=(j<<1)&((1<<m)⑴); int s1=(j<<1|1)&((1<<m)⑴); dp[i][s0]=max(dp[i][s0],dp[i⑴][j]); if(cnt(s1)<=q) dp[i][s1]=max(dp[i][s1],dp[i⑴][j]+a[i]); } } int ans=0; for(int i=0;i<(1<<m);++i) ans=max(ans,dp[n][i]); printf("%d ",ans); return 0; }