正解: 状压 dp(emm...... 据说插头 dp 也可以趴但我不管!!! 不会!!!
解题报告:
...... 我真的太菜了...... 我以为一个小时前要搞完的题目调错误调了一个小时......90 分到 100 我差不多搞了一个小时......
然后这题还是做过的...... 就很气, 觉得确实是要搞下博客没事儿复习下不然做过的题目还花俩小时我真的哭死......
先放上错误的 90 分代码讲一下错哪儿了(因为...... 其实 100 并不难是可以想到的...... 没有太大讲的意义, 主要我太菜了所以才会搞这么久 TT
点我♂看♂沙雕灵巧在线 WA 题
然后错误的点是最后一个点 RE, 开大点儿就 MLE.
来考你一下, 这个程序错哪儿了?
不知道你发现了没有
就是当 j 和 k 可以满足我那个判断的时候, 我的同一个 ztk 会被加进去很多次! 然后 [0] 那个计数菌就会变得很大很大! 然后它就死了!!! 明白了嘛!!!
其实并不是代码只是想折叠下 quq
于是我修改了一下, 判了下重, 就光荣地 WA 了, 还从 90 降到了 30QAQ 爆哭 QAQ
哭到一半! 我突然就! 灵光一现!!! 就想出来正解!!! 就是其实 f 那个数组是不要开的...... 你 484 有点傻......
好然后就放代码趴其实没有改太多并不是很难嘛(...... 对着你做了两小时的程序你再说一遍这句话???
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define rp(i,x,y) for(ll i=x;i<=y;i++)
- #define rl register ll
- ll zt[(1<<15)+50]={},ok[15]={},cnt,dp[15][(1<<15)+50],ans;
- ll read()
- {
- char ch=getchar();ll x=0;bool y=1;
- while(ch!='-' && (ch>'9' || ch<'0'))ch=getchar();
- if(ch=='-')y=0,ch=getchar();
- while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
- return y?x:-x;
- }
- int main()
- {
- ll m=read(),n=read();
- rp(i,0,(1<<n)-1)
- if((i&(i<<1))==0 && (i&(i>>1))==0)
- zt[++cnt]=i;
- rp(i,1,m)
- rp(j,1,n)
- {
- char ch=getchar();
- while(ch!='1' && ch!='0')ch=getchar();
- if(ch=='1')ok[i]=ok[i]|(1<<(n-j));
- }
- rp(i,1,cnt)if((ok[1]&zt[i])==zt[i])dp[1][zt[i]]=1;
- rp(i,2,m)
- rp(k,1,cnt)
- rp(j,1,cnt)
- if(((ok[i]&zt[k])==zt[k]) && ((zt[k] & zt[j])==0))
- dp[i][zt[k]]=(dp[i][zt[k]]+dp[i-1][zt[j]])%100000000;
- rp(i,1,cnt)ans=(ans+dp[m][zt[i]])%100000000;
- printf("%lld",ans);
- return 0;
- }
点♂我♂在线膜拜 hl 大佬
好的那么这次题解只写了十分钟! 我 hin 满意! 以后写题解也不要扯废话浪费时间! over!
P1879 [USACO06NOV]玉米田 Corn Fields 状压 dp
来源: http://www.bubuko.com/infodetail-2802143.html