不管怎么掰都是n*m-1

#include<cstdio>
using namespace std;
int main()
{
freopen("bpmp.in","r",stdin);
freopen("bpmp.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
int ans=(1ll*n*m-)%;
printf("%d",ans);
}

将行状态压缩,枚举哪些行被折成了一条

枚举时,上一次选取的行 与 这一次选取的行 奇偶性不同,这两行才能折到一起

选取列也要求 上一个选的列与这一个选的列奇偶性不同

dp计算这一条上选哪些列

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ans;
int a[][],c[];
int dp(int s)
{
bool f=false;
memset(c,,sizeof(c));
for(int i=;i<n;i++)
if(s&(<<i))
for(int j=;j<m;j++)
c[j]+=a[i][j];
for(int j=;j<m;j++)
if(c[j]>) { f=true; break; }
if(!f) return -2e9;
int c0=,c1=,x;
for(int i=;i<m;i++)
if(i&) c1=max(c[i]+c0,c1);
else c0=max(c[i]+c1,c0);
return max(c1,c0);
}
void dfs(int now,int last,int state)
{
if(now==n)
{
ans=max(ans,dp(state));
return;
}
if(last==- || ((now-last)&)) dfs(now+,now,state|(<<now));
dfs(now+,last,state);
}
int main()
{
freopen("cfyw.in","r",stdin);
freopen("cfyw.out","w",stdout);
scanf("%d%d",&n,&m);
ans=-2e9;
for(int i=;i<n;i++)
for(int j=;j<m;j++)
scanf("%d",&a[i][j]),ans=max(ans,a[i][j]);
if(ans>) dfs(,-,);
printf("%d",ans);
}

推公式+除法分块

http://www.cnblogs.com/TheRoadToTheGold/p/6696450.html

#include<cstdio>
#include<algorithm>
#define N 10000001
#define mod 998244353
using namespace std;
int p[],phi[N],cnt;
long long sum[N];
bool vis[N];
void pre(int n)
{
phi[]=;
for(int i=;i<=n;i++)
{
if(!vis[i])
{
vis[i]=true;
phi[i]=i-;
p[++cnt]=i;
}
for(int j=;j<=cnt;j++)
{
if(i*p[j]>n) break;
vis[i*p[j]]=true;
if(i%p[j]==)
{
phi[i*p[j]]=phi[i]*p[j];
break;
}
else phi[i*p[j]]=phi[i]*(p[j]-);
}
}
for(int i=;i<=n;i++) sum[i]=sum[i-]+phi[i];
}
int main()
{
freopen("hoip.in","r",stdin);
freopen("hoip.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
pre(min(n,m));
long long ans=;
long long j;
for(long long i=;i<=min(n,m);i=j+)
{
j=min(n/(n/i),m/(m/i));
ans=(ans+(sum[j]-sum[i-])*(n/i)%mod*(m/i)%mod)%mod;
}
printf("%I64d",ans);
}

最新文章

  1. JVM_七种垃圾收集器介绍
  2. redis 原子增一的妙用
  3. Virtual Box和Linux的网络配置盲记
  4. 每天一个linux命令(40):watch命令
  5. [git]Git与Repo入门
  6. C++写一个排列组合小程序
  7. python 替换windows换行符为unix格式
  8. MediaChooser图库浏览器
  9. 懵懵懂懂初识J2EE
  10. 创建 OVS vlan100 netwrok - 每天5分钟玩转 OpenStack(137)
  11. 记一次Java的内存泄露分析
  12. [20160711][VS2012配置OpenCV2.4.9]
  13. 【SpringCloud】HystrixCommand的threadPoolKey默认值及线程池初始化
  14. 51nod--1174 区间中最大的数 (RMQ)
  15. [转]搞个这样的 APP 要多久
  16. SRA秘钥生成与解密
  17. PKU Judge Online 安装指南
  18. APS审核经验+审核资料汇总——计算机科学与技术专业上海德语审核
  19. java工具类-读配置文件
  20. 安装scrapy 出错 building &#39;twisted.test.raiser&#39; extension error: Microsoft Visual C++ 14.0 is required.

热门文章

  1. dubbo源码分析1——负载均衡
  2. lintcode-424-逆波兰表达式求值
  3. WPF和Expression Blend开发实例:Loading动画
  4. 防御 XSS 的七条原则
  5. QCryptographicHash实现哈希值计算,支持多种算法
  6. Android自动化 -- sendevent/getevent 用法
  7. 深入理解JVM一配置参数
  8. 【刷题】HDU 4966 GGS-DDU
  9. 【BZOJ1458】【洛谷4311】士兵占领(网络流)
  10. redis的自带VM(虚拟内存)