现在代码能力没上升,倒是越来越会找水题了(比例题还水的裸题你值得拥有)
这网站不是针对竞赛的,所以时空限制都很宽松
然后就让我水过去了
对于每个点,包括自己的前m个元素是否取都是一种状态,所以状压一下(才1024不要怂)
#include <cstdio>
int n,m,q;
int a[];
int dp[][];
int max(int a,int b){return(a<b)?b:a;}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
int add=<<(m-);
for(int i=;i<=n;i++)
for(int j=;j<=(add<<)-;j++)
{
int k=j,sum=;
while(k)
sum+=k&,k>>=;
if(sum>q) continue;
dp[i][j>>]=max(dp[i][j>>],dp[i-][j]);
if(sum==q && !(j&)) continue;
dp[i][(j>>)+add]=max(dp[i][(j>>)+add],dp[i-][j]+a[i]);
}
int ans=;
for(int j=;j<=add<<;j++)
ans=max(ans,dp[n][j]);
printf("%d",ans);
return ;
}
先用这道题熟悉一下状压的套路吧,到时候还要补轮廓线= =
调试要点:
1.位运算
2.位运算
3.位运算
(其实就是所有左移右移都要加括号,为了这玩意儿我爆了N发OJ)