2021牛客寒假算法基础集训营6 网格(思维+线性dp)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了2021牛客寒假算法基础集训营6 网格(思维+线性dp),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1634字,纯文字阅读大概需要3分钟。
内容图文
![2021牛客寒假算法基础集训营6 网格(思维+线性dp)](/upload/InfoBanner/zyjiaocheng/602/cf182c4b92ec42a585b1d41044db84f3.jpg)
https://ac.nowcoder.com/acm/contest/9986/E
题意:
有一个网格,每一个位置可以选上下左右四个方向的数,但是选了上就不能选下,选了左就不能选右。
同时如果两个相邻的位置,如果其中一个方向选了右,一个选了左,互相选到了对方,就对答案产生w(a1^a2)的贡献
其中w(x):x+popcnt(x).
思路:其实可以发现一个位置选上下和左右是分割开的,可以分开统计出来。
于是行列分开处理,对于每一列先转移出一个最优状态,累加到答案。
然后再对每一行转移出一个最优状态,再累加到答案。
dp[i][j][0/1]:表示第i行第j个数选左边/右边的最大贡献和。
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e3+1000;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL a[maxn][maxn];
LL dp1[maxn][maxn][2],dp2[maxn][maxn][2];
LL get(LL x){
LL temp=x;LL sum=0;
while(x>0){
if(x&1) sum++;
x>>=1;
}
return temp+sum;
}
int main(void)
{
cin.tie(0);std::ios::sync_with_stdio(false);
LL n,m;cin>>n>>m;
for(LL i=1;i<=n;i++){
for(LL j=1;j<=m;j++){
cin>>a[i][j];
}
}
LL ans=0;
for(LL i=1;i<=n;i++){
for(LL j=2;j<=m;j++){
dp1[i][j][0]=max(dp1[i][j-1][1]+get(a[i][j-1]^a[i][j]),dp1[i][j-1][0]);
dp1[i][j][1]=max(dp1[i][j-1][1],dp1[i][j-1][0]);
}
ans+=max(dp1[i][m][0],dp1[i][m][1]);
}
for(LL j=1;j<=m;j++){
for(LL i=2;i<=n;i++){
dp2[i][j][0]=max(dp2[i-1][j][1]+get(a[i-1][j]^a[i][j]),dp2[i-1][j][0]);
dp2[i][j][1]=max(dp2[i-1][j][1],dp2[i-1][j][0]);
}
ans+=max(dp2[n][j][0],dp2[n][j][1]);
}
cout<<ans<<"\n";
return 0;
}
内容总结
以上是互联网集市为您收集整理的2021牛客寒假算法基础集训营6 网格(思维+线性dp)全部内容,希望文章能够帮你解决2021牛客寒假算法基础集训营6 网格(思维+线性dp)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。