首页 > 代码库 > T7315 yyy矩阵折叠(长)
T7315 yyy矩阵折叠(长)
题目背景
全场基本暴零
题目描述
输入输出格式
输入格式:
如图
输出格式:
如图
输入输出样例
输入样例#1:
2 21 -23 -4
输出样例#1:
4
输入样例#2:
2 51 -2 -3 4 -56 -7 -8 9 -10
输出样例#2:
20
说明
如图
DFS行,状压DP列
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #include<stack> 8 #include<cstdlib> 9 using namespace std;10 const int maxn=0x7fffff;11 inline void read(int &n)12 {13 char c=‘+‘;int x=0;bool flag=0;14 while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;}15 while(c>=‘0‘&&c<=‘9‘)16 x=(x<<1)+(x<<3)+c-48,c=getchar();17 flag==1?n=-x:n=x;18 }19 int n,m; 20 int a[99][501];21 int ans=-maxn;22 int cur[501];23 int pos2(int x)24 {25 return (1<<x);26 }27 int dp(int zt)28 {29 memset(cur,0,sizeof(cur));30 int ou,ji;31 for(int i=1;i<=n;i++)32 if(zt&pos2(i))33 for(int j=1;j<=m;j++)34 cur[j]+=a[i][j];35 bool flag=1;36 for(int i=1;i<=m;i++)37 if(cur[i]>0)38 {39 flag=0;40 break;41 }42 if(flag)43 return -maxn;44 ou=0;ji=0;45 for(int i=1;i<=m;i++)46 {47 if(i&1)48 {49 int x=cur[i]+ou;50 ji=max(ji,x);51 }52 else53 {54 int x=cur[i]+ji;55 ou=max(ou,x);56 }57 }58 return max(ou,ji);59 }60 void dfs(int pos,int last,int zt)61 {62 if(pos==n+1)63 {64 ans=max(ans,dp(zt));65 return ;66 }67 68 if(last==-1||(pos-last)&1)69 dfs(pos+1,pos,zt|pos2(pos));70 dfs(pos+1,last,zt);71 }72 int main()73 {74 read(n);read(m);75 for(int i=1;i<=n;i++)76 for(int j=1;j<=m;j++)77 {78 read(a[i][j]);79 ans=max(ans,a[i][j]);80 }81 if(ans<0) 82 cout<<ans;83 else84 {85 dfs(1,-1,0);86 printf("%d",ans);87 }88 return 0;89 }
T7315 yyy矩阵折叠(长)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。