1172. Ship Routes
2024-08-26 13:30:58
http://acm.timus.ru/problem.aspx?space=1&num=1172
水题DP 大整数直接上java
代码:
import java.math.BigInteger;
import java.util.Scanner; public class Main { /**
* @param args
*/
static final int N = 35; public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
BigInteger[][][][] dp = new BigInteger[N][N][N][4];
int n = in.nextInt();
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
for (int l = 0; l <= n; ++l) {
for (int k = 1; k <= 3; ++k) {
dp[i][j][l][k]=BigInteger.ZERO;
}
}
}
}
dp[0][0][0][1] = BigInteger.ONE;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
for (int l = 0; l <= n; ++l) {
for (int k = 1; k <= 3; ++k) {
if (dp[i][j][l][k].compareTo(BigInteger.ZERO) == 1) {
if (k != 1 && i < n) {
dp[i + 1][j][l][1] = dp[i + 1][j][l][1]
.add(dp[i][j][l][k].multiply(BigInteger
.valueOf(Math.max(1, n - i - 1))));
}
if (k != 2 && j < n) {
dp[i][j + 1][l][2] = dp[i][j + 1][l][2]
.add(dp[i][j][l][k].multiply(BigInteger
.valueOf(n - j)));
}
if (k != 3 && l < n) {
dp[i][j][l + 1][3] = dp[i][j][l + 1][3]
.add(dp[i][j][l][k].multiply(BigInteger
.valueOf(n - l)));
}
}
}
}
}
}
System.out.println(dp[n][n][n][1].divide(BigInteger.valueOf(2L)));
} }
最新文章
- css兼容性大坑
- WPF直接用Window.Close直接关闭窗口导致不能完全退出的问题
- flex 4.6 移动开发 app.xml配置说明
- 【C++沉思录】代理类
- PrincipalView的使用参数
- [PeterDLax著泛函分析习题参考解答]第7章 Hilbert 空间结果的应用
- 000 Python之禅
- 【Java并发系列03】ThreadLocal详解
- Spring+redis整合遇到的问题集以及注意事项
- 在Windows上安装FFmpeg程序的方法(you-get下载视频必备程序)
- Centos7的目录结构
- 使用代理实现对C# list distinct操作
- java反射查看jar包中所有的类名方法名
- javascript 小实例,求和的方法sumFn
- 编写装饰器实现python请求错误重试功能
- Object类型的转为String类型
- Linux平台下停止后台进程脚本编写
- 2017-2018 ACM-ICPC, Asia Daejeon Regional Contest C(记忆化搜索)
- BZOJ5120 无限之环(费用流)
- Laravel 配置文件操作方法
热门文章
- .Net 中HashTable,HashMap 和 Dictionary<;key,value>; 和List<;T>;和DataTable的比较
- NET中的类型和装箱/拆箱原理
- 关于在官网上查看和下载特定版本的webrtc代码
- asp.net 加载xml到menu
- JQ的live(),on(),deletage(),bind()几个的区别
- Entity Framework 第八篇 结构优化
- Java线程锁一个简单Lock
- iOS 键盘类型定制归纳
- createjs 更新
- aws在线技术峰会笔记-电商解决方案