为什么说恶心,状态压缩就算了,而且转移的时候还要借助dfs - -!借助dfs就算了,转移方式有很多啊,转移要用到的参数有5个啊!!!一共32种情况啊!!一个都不能少啊,少了一个你就wa啊!!情况多也算了啊!!!最tm坑爹的就是还要用滚动数组啊!!否则你就F5F5F5坐等超时空啊!!!有木有。。。
最恶心的就是,你看别人的代码你还看不懂啊!!还是要靠自己想啊!!别人代码精简的一b,根本不留任何踪迹让你理解,传说中的IQ再高也迷茫啊!!迷茫啊!!!
想了3个晚上,哥终于开窍了,调试了一个上午。。。终于a了,终于a了。。。
哥还是说说这题的方法吧~~~
dp[?][x][y],?表示的是dp进行到第几行,并且前面的行都已经满足情况,这里说的满足情况指的是如果你要放方块的话,一定不会和前面的行有关;第二,x所在的行在行内满足情况,意思就是你不能单纯的在x行内放方块;y表示下一行的状态;这样的话就能一行一行推下去;
根据哥目测,对于一次状态转移,一共有4种情况;
1.直接跳过去;2.i-1和i之间放一个;3.i和i+1之间竖着放一个;4.在第i行横着放一个。
这样说很简单,但是还要知道这4种情况到底什么时候可以,什么时候不可以,这就需要5个参数,就是哥代码里的c1,c2,c3,c4,c5;要想清楚还是有一定难度的~
这是道好题,希望有实力的ACM后辈们好好品味之~
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;
#ifdef _WIN32
#define i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
#define i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif
#define FOR(i,a,b) for( int i = (a) ; i <= (b) ; i ++)
#define FF(i,a) for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a) for( int i = (a)-1 ; i >= 0 ; i --)
#define S64(a) scanf(in64,&a)
#define SS(a) scanf("%d",&a)
#define LL(a) ((a)<<1)
#define RR(a) (((a)<<1)+1)
#define SZ(a) ((int)a.size())
#define PP(n,m,a) puts("---");FF(i,n){FF(j,m)cout << a[i][j] << ' ';puts("");}
#define pb push_back
#define CL(Q) while(!Q.empty())Q.pop()
#define MM(name,what) memset(name,what,sizeof(name))
#define read freopen("in.txt","r",stdin)
#define write freopen("out.txt","w",stdout)
const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 10e-10;
const double pi = acos(-1.0);
const int maxn = 7;
const int maxc = 77;
int dp[1<<maxn][1<<maxn];
int get[1<<maxn][1<<maxn];
int xx[maxc];
string s[maxc];
int a[maxc];
int m,n;
int change(string r)
{
int re=0;
FF(i,r.length())
{
re<<=1;
if(r[i]==42)
{
re|=1;
}
}
return re;
}
void ex()
{
a[0] = (1<<n)-1;
FOR(i,1,m)
{
a[i] = change(s[i]);
}
a[m+1] = (1<<n)-1;
a[m+2] = (1<<n)-1;
return ;
}
void dfs(int k,int now,int to,int x,int y,int add)
{
if(k>n+1)
{
return ;
}
if(k==n+1)
{
get[x][y] = min(get[x][y],dp[now][to]+add);
// cout<<"******"<<x<<" | "<<y<<" | "<<get[x][y]<<endl;
return ;
}
int c1=(now & xx[k])?1:0;
int c2=(x & xx[k])?1:0;
int c3=(y & xx[k])?1:0;
int c4=(x & xx[k+1])?1:0;
int c5=(x & xx[k-1])?1:0;
// cout<<"yy"<<oct<<y<<endl;
// cout<<k<<" | "<<c1<<c2<<c3<<c4<<c5<<endl;
if(!c2 && !c4)
{
dfs(k+2,now,to,x+xx[k]+xx[k+1],y,add+1);
}
if(!c1 && !c2)
{
dfs(k+1,now,to,x+xx[k],y,add+1);
}
if(!c2 && !c3)
{
dfs(k+1,now,to,x+xx[k],y+xx[k],add+1);
}
if( (k==1 || c5 || c2) && !(!c1 && !c2) )
{
dfs(k+1,now,to,x,y,add);
}
return ;
}
void init()
{
FF(i,1<<n) FF(j,1<<n)
{
dp[i][j] = inf;
get[i][j] = inf;
}
return ;
}
void end()
{
FF(i,1<<n) FF(j,1<<n)
{
dp[i][j] = get[i][j];
}
FF(i,1<<n) FF(j,1<<n)
{
get[i][j] = inf;
}
return ;
}
int start()
{
MM(a,0);
ex();
xx[0] = 0;
for(int i=1;i<=n+1;i++)
{
xx[i] = 1<<(i-1);
}
init();
dp[(1<<n)-1][a[1]] = 0;
for(int i=0;i<=m;i++)
{
// cout<<"cen == "<<i<<endl;
FF(u,1<<n) if( !( ~u & a[i] ) )
{
FF(e,1<<n) if( dp[u][e] != inf && !(~e & a[i+1]) )
{
// cout<<"- -!"<<oct<<u<<" | "<<oct<<e<<endl;
// cout<<"i+2=="<<i+2<<" | "<<oct<<a[i+2]<<endl;
dfs(1,u,e,e,a[i+2],0);
}
}
end();
}
int ans = inf;
FF(i,1<<n) FF(j,1<<n)
{
ans = min(ans,dp[i][j]);
}
return ans;
}
int main()
{
while(cin>>m>>n)
{
FOR(i,1,m)
{
cin>>s[i];
}
cout<<start()<<endl;
}
return 0;
}
分享到:
相关推荐
SGU 385,我写的程序,一道DP题,跟概率有关
SGU推荐题目分类,适合初次使用sgu的编程爱好者使用!
SGU 390 AC源码,数位统计的难题
SGU题库整合 Volume (200 - 299) pdf版
辛苦整理所得,分略多,绝对值得,sgu完整题库(530个网页,还有试题难度排序)。lnddszp[at]gmail[dot]com
SGU离线题库(2015-6-8整理),图片可以显示。。
sgu oj上的 101-121 的AC代码
SGU-801综合通讯接入装置使用说明书
SGU 103AC 代码 质量有保证!
SGU 333 集训队AC程序,秒过,CPP
sgu ##这是一个将我的 sol 问题存储到 acm.sgu.ru 的存储库
SGU题库 Volume (100-199) pdf整合版
pku sgu 经典图论题解答, 多种方法解答经典图论题, 附源代码
ID 标题 交流电 A + B 18881 互质 7697 第3分部 6906 总和 6185 日历 4336 画线 4159 987654321问题 4014 肉饼 3998 几乎素数 3845 a ^ b-b ^ a 3673 骨牌 3621 花小店 3417 ...1884
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝会超时 poj2455 ...
下载调度程序,用于低带宽环境。 全天扩展下载量
“#babylonjs-sgu”
HJVXJVHSKVH JHDK JH DFKSDYFS DVJDSVXCVXCVZXCVZXCV
SGU-用于搜索github用户的输入表单- 描述 您可以通过输入一些文本来找到github用户。 然后,您将拥有一个用户名和用户图标。 仅显示搜索关键字和用户名之间的数据。 库版本 下一个v10.0.7 Reactv17.0.1 react-dom ...