思路:状态压缩dp,f[i][j[[k]代表i行j列这个格子,连续的状态为k,这个连续的状态是什么?就是下图

X格子代表我当前走到的地方,而这里的状态就是红色部分,也就是连续的一段n的状态,我们是分每一位计算的,这样就可以转移了,注意,当当前点在最下面的时候要额外计算一个与1的贡献。

坑爹,inf设小了只有30分。

 #include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
const ll inf=1e18;
ll f[][],bin[],sum[],ans;
ll a[][],b[][],c1[][],c2[][];
ll s[];
int n,m;
ll read(){
ll t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-')f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
ll query(int id,int j,int st){
int top=;
for (int i=;i<=n;i++){
s[++top]=st%;
st/=;
}
s[]=s[top];s[top+]=s[];
ll res=;
for (int i=;i<=n;i++)
res+=((s[i]*bin[id])^(a[i][j]&bin[id]))*b[i][j];
for (int i=;i<=n;i++)
res+=((s[i]*bin[id])^(bin[id]*s[i+]))*c2[i][j];
return res;
}
void dp(int id){
int tot=(<<n)-,cnt=;
for (int i=;i<=n*m;i++)
for (int j=;j<=tot;j++)
f[i][j]=inf;
for (int i=;i<=tot;i++)
f[n][i]=query(id,,i);
for (int j=;j<=m;j++)
for (int i=;i<=n;i++){
int now=(j-)*n+i,pre=now-;
for (int st=;st<=tot;st++){
int st1=st&sum[n-],lst=((st&bin[n-])>),ths=((st&bin[n-])>);
ll tmp=;
if (i!=) tmp+=((lst^ths)*c2[i-][j])*bin[id];
if (i==n) tmp+=(((st&bin[])^ths)*c2[i][j])*bin[id];
tmp+=((a[i][j]&bin[id])^(ths*bin[id]))*b[i][j];
for (int k=;k<=;k++){
int st2=st1*+k,beh=((st2&bin[])>);
ll tmp2=(beh^ths)*bin[id]*c1[i][j-];
f[now][st]=std::min(f[now][st],f[pre][st2]+tmp+tmp2);
}
}
}
ll Tmp=inf;
for (int i=;i<=tot;i++)
Tmp=std::min(f[n*m][i],Tmp);
ans+=Tmp;
}
int main(){
n=read();m=read();bin[]=;
for (int i=;i<=;i++) bin[i]=bin[i-]*;sum[]=bin[];
for (int i=;i<=;i++) sum[i]=sum[i-]+bin[i];
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
a[i][j]=read();
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
b[i][j]=read();
for (int i=;i<=n;i++)
for (int j=;j<m;j++)
c1[i][j]=read();
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
c2[i][j]=read();
for (int i=;i<=;i++){
dp(i);
}
printf("%I64d\n",ans);
fclose(stdin);fclose(stdout);
return ;
}

最新文章

  1. NetMQ(三): 发布订阅模式 Publisher-Subscriber
  2. (原)android的alertdialog中加入edittext但是不弹出软键盘等问题的解决与原因
  3. FSL - MELODIC
  4. Python装饰器(decorator)
  5. Java 不定长度参数
  6. JavaScript 中的非真值
  7. 常用渗透性测试工具(Tools for penetration testing)
  8. webpack React+ES6
  9. python pandas 数据处理
  10. HTML5 语义元素、迁移、样式指南和代码约定
  11. Unity CommandInvokationFailure: Failed to re-package resources. 解决方案
  12. github设置添加SSH
  13. C++实现控制台版2048
  14. Windows 安装 Vue
  15. 如何在Microsoft Word里面插入图片作为背景/封面?
  16. 【Windows】添加定时任务不执行
  17. 读取excel日期数据问题
  18. springboot整合fastJson遇到重定向问题
  19. Bootstrap——网站添加字体图标
  20. Django基础(二)

热门文章

  1. 将vs2012建的项目转换为vs2010项目
  2. JS-异常处理
  3. Linux下的bc计算器
  4. Java使用poi包读取Excel文档
  5. Jmeter接口测试案例实践(一)
  6. php增删改查,自己写的demo
  7. .net对文件的操作之对文件目录的操作
  8. FreeMarker辅助
  9. 动态更新UI的方式
  10. java下io文件切割合并功能