caioj1496: [视频]基于连通性状态压缩的动态规划问题:Manhattan Wiring
2024-08-31 14:00:43
%%%%orz苏大佬 虽然苏大佬的baff吸不得,苏大佬的梦信不得,但是膜苏大佬是少不得的囧
这题还是比较有收获的 哼居然有我不会做的插头DP
自己yy了下,2表示属于2的插头,3表示3的插头
假如当前是0点,并且没有左上连向,那么可以不放插头,也可以放2放3,否则就是常规操作
假如是障碍那就不能有插头
然后假如是2和3点,就可以放个单插头,或者直接继承前面的插头
我觉得很OK啊。。。然后就不会记录ans了
????黑人问号啊,怎么判是否结束了啊
写了各种异或判断是否当前状态把四个位置都放了,然后。。就只能过这个↓
2 3
2 2 0
0 3 3
直接去%苏大佬的code,发现她是这么写的:
ans=;
work();
for(int i=;i<=dp[now].size;i++)
{
ans+=dp[now].num[i];//将所有可行的方案加入ans
}
printf("%lld\n",ans>?ans-:);
她怎么能直接把状态的最小值累加啊???
调试了一下发现,这个栈里面的元素要么只有一个要么没有要你这个for何用啊
彻底懵逼。。直接去膜拜 终于懂了
是因为到最后肯定只有一个状态,就是0(也就是匹配完成),假如不匹配完成那么就不会成功继承。
那我现在的感觉是其他题是不是也一样?假如我让它不合法就不继承好像可以一样做欸
upd:我在做下一题的时候发现我好像沙茶了,因为每道题情况不一样,对于这题而言,它不需要形成回路,并且可以有空格不行经,使得它在转移的时候可以空转移,所以能够无需特判直接转移到末尾
整理下思路,一开始我想的是分开算2和3的长度,这个很难实现,因为它们不相交所以我只需要求放了插头的位置数就行了,对于继承答案可以直接转移到最后一个位置,中途继承判合法就行了
为什么每次写s=set_bracket(s,j,q);都特别想笑。。。我也想把LCT改成YZH
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const LL mod=; int n,m;
int mp[][];
struct node
{
LL mn[];
int top;LL hash[],sta[];
void pha(int s,LL mmin)
{
int x=s%mod;
while(hash[x]!=&&sta[hash[x]]!=s)x=(x+)%mod;
if(hash[x]==)sta[++top]=s,hash[x]=top;
mn[hash[x]]=min(mn[hash[x]],mmin);
}
void clean()
{
top=;
memset(mn,,sizeof(mn));
memset(hash,,sizeof(hash));
}
}dp[];
LL get_bracket(LL s,LL p)
{
return (s>>((p-)*))&;
}
LL set_bracket(LL s,LL p,LL v)
{
s^=(get_bracket(s,p)<<((p-)*));
s^=(v<<((p-)*));
return s;
}
int pre,now;
void Plug_DP()
{
pre=,now=;
dp[now].clean();dp[now].pha(,);
for(LL i=;i<=n;i++)
{
for(LL j=;j<=m;j++)
{
swap(pre,now);dp[now].clean();
for(int k=;k<=dp[pre].top;k++)
{
LL s=dp[pre].sta[k],mn=dp[pre].mn[k];
LL p=get_bracket(s,j),q=get_bracket(s,j+); if(mp[i][j]==)
{
if(p==&&q==)dp[now].pha(s,mn);
}
else if(mp[i][j]==)
{
if(p==&&q==)
{
s=set_bracket(s,j,);
s=set_bracket(s,j+,);
dp[now].pha(s,mn);
if(mp[i][j+]!=&&mp[i+][j]!=)
{
s=set_bracket(s,j,);
s=set_bracket(s,j+,);
dp[now].pha(s,mn+);
s=set_bracket(s,j,);
s=set_bracket(s,j+,);
dp[now].pha(s,mn+);
}
}
else if(p==&&q>)
{
if(mp[i+][j]!=)
{
s=set_bracket(s,j,q);
s=set_bracket(s,j+,);
dp[now].pha(s,mn+);
}
if(mp[i][j+]!=)
{
s=set_bracket(s,j,);
s=set_bracket(s,j+,q);
dp[now].pha(s,mn+);
}
}
else if(p>&&q==)
{
if(mp[i+][j]!=)
{
s=set_bracket(s,j,p);
s=set_bracket(s,j+,);
dp[now].pha(s,mn+);
}
if(mp[i][j+]!=)
{
s=set_bracket(s,j,);
s=set_bracket(s,j+,p);
dp[now].pha(s,mn+);
}
}
else if(p>&&q>)
{
if(p==q)
{
s=set_bracket(s,j,);
s=set_bracket(s,j+,);
dp[now].pha(s,mn+);
}
}
}
else
{
if(p==&&q==)
{
if(mp[i][j+]==||mp[i][j+]==mp[i][j])
{
s=set_bracket(s,j,);
s=set_bracket(s,j+,mp[i][j]);
dp[now].pha(s,mn+);
}
if(mp[i+][j]==||mp[i+][j]==mp[i][j])
{
s=set_bracket(s,j,mp[i][j]);
s=set_bracket(s,j+,);
dp[now].pha(s,mn+);
}
}
if((p==&&q==mp[i][j])||(p==mp[i][j]&&q==))
{
s=set_bracket(s,j,);
s=set_bracket(s,j+,);
dp[now].pha(s,mn+);
}
}
}
}
for(int k=;k<=dp[now].top;k++)
dp[now].sta[k]<<=;
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==&&m==)break;
memset(mp,,sizeof(mp));
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
scanf("%d",&mp[i][j]);
if(mp[i][j]==||mp[i][j]==)mp[i][j]^=;
}
}
Plug_DP();
printf("%lld\n",(dp[now].top==)?:(dp[now].mn[]-));
}
return ;
}
最新文章
- jquery获取table的行数、列数
- We are doomed, and RPC does not help
- 从源码的角度解析View的事件分发
- 一步步学习NHibernate(7)——HQL查询(1)
- pycharm 修改新建文件时的头部模板(默认为__author__=&#39;...&#39;)
- WinForm中控件位置不随窗体大小的变化而改变
- maven如何修改本地仓库与中央仓库
- Python爬取视频(其实是一篇福利)
- webservice入门简介
- LEDAPS1.3.0版本移植到windows平台----HuCsm云掩膜模块
- Windows 2008 asp.net 配置
- python利用requests和threading模块,实现多线程爬取电影天堂最新电影信息。
- mybatis学习笔记1.零碎记录
- c++屏蔽Win10系统快捷键
- Github(远程仓库) 2
- mysql解决大量time_wait
- python中的命名元组namedtuple
- SignalR2结合ujtopo实现拓扑图动态变化
- Java超类-java.lang.object
- python面向对象之类成员
热门文章
- UI常用网站
- MessageDigest的功能及用法(加密解密)
- BZOJ2134: 单选错位(期望乱搞)
- 移动端web开发初探之Vuejs的简单实战
- C++中内存分配、函数调用和返回值问题
- C# 3.0新加特性
- SDL2源代码分析
- mysql出错ERROR 2003 (HY000): Can&#39;t connect to MySQL server on &#39;localhost&#39; (10061)
- python海龟的使用
- 将JavaBean对象/List或Set或Map对象转成JSON方式