首页 > 代码库 > 【BZOJ 3195 】[Jxoi2012]奇怪的道路 装压dp
【BZOJ 3195 】[Jxoi2012]奇怪的道路 装压dp
受惯性思维的影响自动把二进制状态认为是连与不连.........
我们这里二进制状态表示的是奇偶，这样的话我们f[i][j][k]表示的就是前i个城市用了j个边他前k个城市的奇偶状态，然后想想怎么转移，我们要是深搜就会从一开始一直搜每搜到一个最终状态就是一个答案，然后状态转移同理，我们f[1][0][0]是1，往后转移，到了就加，就是了。
坑：I.取模.....
||.我们转移的时候一定不要有重状态，三层for的顺序十分关键
|||.转移的时候最远的一位一定要是0
#include <cstdio> #define P 1000000007 #define r register using namespace std; int n,full,m,K,f[35][35][1030]; int main() { scanf("%d%d%d",&n,&m,&K); full=(1<<(K+1))-1; f[1][0][0]=1; for(r int i=1;i<=n;i++) { r int lim=i<(K+1)?i:(K+1); for(r int j=1;j<lim;j++) for(r int l=m;l>=0;l--) for(r int k=1;k+l<=m;k++) for(r int w=0;w<=full;w++) f[i][l+k][w^((k&1)<<j)^(k&1)]=(f[i][l+k][w^((k&1)<<j)^(k&1)]+f[i][l][w])%P; for(r int w=0;w<=full;w++) if(lim<(K+1)||((w&(1<<K))==0)) for(r int l=0;l<=m;l++) f[i+1][l][w<<1]=f[i][l][w]; } printf("%d",f[n][m][0]); }
【BZOJ 3195 】[Jxoi2012]奇怪的道路 装压dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。