注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

USACO 6.1 Postal Vans(vans)  

2010-07-11 23:25:52|  分类: usaco |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
直接插头dp,再次膜拜cdq大牛,话说插头dp理解的还不是很好,有空再看看,而且发现java的BigInteger不是一般的快啊,犀利啊

import java.math.*;
import java.io.*;
import java.util.*;

public class vans {
static int n = 4, t = 0;
static int[] to = new int[50], d = new int[50];
static int[][] dd = new int[50][20];
static BigInteger[][] f = new BigInteger[1001][3661];

public static void main(String[] args) {
int nn = 0;
try {
BufferedReader in = new BufferedReader(new FileReader("vans.in"));
nn = Integer.parseInt(in.readLine());
in.close();
} catch (Exception e) {
}
int k = 0, kk = 1 << ((n + 1) << 1), ll, x, i, j, jj;
for (i = 0; i < kk; i++) {
for (x = i, j = 0, k = 0; x != 0; x >>= 2, j++) {
ll = x & 3;
if (ll == 1)
d[k++] = j;
if (ll == 2)
if ((k--) != 0) {
dd[t][j] = d[k];
dd[t][d[k]] = j;
} else
break;
if (ll == 3) {
k = 1;
break;
}
}
if (k == 0)
to[t++] = i;
}
for (i = 0; i <= n; ++i)
f[i] = new BigInteger[3661];
for (i = 0; i <= n; ++i)
for (j = 0; j < 3661; ++j)
f[i][j] = BigInteger.ZERO;
f[n][0] = BigInteger.valueOf(2);
for (i = 0; i < nn; i++) {
for (j = 0; j < t; j++) {
f[0][to[j] << 2] = f[n][to[j]];
}
for (jj = 1; jj <= n; jj++) {
for (int j2 = 0; j2 < 661; j2++)
f[jj][j2] = BigInteger.ZERO;
for (j = 0; j < t; j++) {
int x1 = to[j] << 2 >> (jj << 1) & 3, x2 = to[j] >> (jj << 1) & 3;
int t1 = 1 << (jj << 1) >> 2, t2 = 1 << (jj << 1);
if (x1 == x2) {
if (x1 == 0)
f[jj][to[j] ^ t1 ^ (t2 << 1)] = f[jj][to[j] ^ t1
^ (t2 << 1)].add(f[jj - 1][to[j]]);
else if (x1 == 1)
f[jj][to[j] ^ t1 ^ t2 ^ (3 << (dd[j][jj] << 1))] = f[jj][to[j]
^ t1 ^ t2 ^ (3 << (dd[j][jj] << 1))]
.add(f[jj - 1][to[j]]);
else
f[jj][to[j] ^ (t1 << 1) ^ (t2 << 1)
^ (3 << (dd[j][jj - 1] << 1))] = f[jj][to[j]
^ (t1 << 1)
^ (t2 << 1)
^ (3 << (dd[j][jj - 1] << 1))]
.add(f[jj - 1][to[j]]);
} else if (!(x1 != 0 && x2 != 0)) {
f[jj][to[j] ^ ((x1 ^ x2) << (jj << 1))
^ ((x1 ^ x2) << (jj << 1) >> 2)] = f[jj][to[j]
^ ((x1 ^ x2) << (jj << 1))
^ ((x1 ^ x2) << (jj << 1) >> 2)]
.add(f[jj - 1][to[j]]);
f[jj][to[j]] = f[jj][to[j]].add(f[jj - 1][to[j]]);
} else if (x1 == 2)
f[jj][to[j] ^ (t1 << 1) ^ t2] = f[jj][to[j] ^ (t1 << 1)
^ t2].add(f[jj - 1][to[j]]);
else if (i == nn - 1 && jj == n
&& (to[j] ^ t1 ^ (t2 << 1)) == 0)
f[jj][0] = f[jj][0].add(f[jj - 1][to[j]]);
}
}
}
try {
PrintWriter out = new PrintWriter(new BufferedWriter(
new FileWriter("vans.out")));
out.println(f[n][0]);
out.close();
} catch (Exception e) {
}
}
}
  评论这张
 
阅读(831)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018