【专业找水题】状压dp最水题,没有之一

题目链接

现在代码能力没上升,倒是越来越会找水题了(比例题还水的裸题你值得拥有)

这网站不是针对竞赛的,所以时空限制都很宽松

然后就让我水过去了

对于每个点,包括自己的前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)

上一篇:特征的Attribute Only选项


下一篇:ORACLE 移动数据文件 控制文件 重做日志文件