时间海

题目描述（动态规划,动规,dp，递归费用流）设有 N×N 的方格图 ( N≤9 ) ，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0。如下图所示（见样例）: A 0 0 0 0 0 0 0 0 0 0 13 0 0 6 0 0 0 0 0 0 7 0 0 0 0 0 0 14 0 0 0 0 0 21 0 0 0 4 0 0 0 0 15 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B 某人从图的左上角的 A 点出发，可以向下行走，也可以向右走，直到到达右下角的 B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。 此人从 A 点到 B 点共走两次，试找出 2 条这样的路径，使得取得的数之和为最大。 输入格式输入的第一行为一个整数 N（表示 N×N 的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的 ...

最少硬币问题（动态规划）设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，计算找钱m的最少硬币数。 Input输入数据第一行中只有1个整数给出n的值,第2行起每行2个数，分别是T[j]和Coins[j]。最后1行是要找的钱数m。 Output输出数据只有一个整数，表示计算出的最少硬币数。问题无解时输出-1。 Sample Input31 32 35 318 Sample Output5 代码#include<bits/stdc++.h> using namespace std; #define MAXN 0x3f3f3f3f int dp[20005]; int main(){ int n,m,T[20005],Coins[20005]; cin>> ...

P1002 过河卒（动态规划，dp）题目描述棋盘上 AA 点有一个过河卒，需要走到目标 BB 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 CC 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示，AA 点 (0, 0)(0,0)、BB 点 (n, m)(n,m)，同样马的位置坐标是需要给出的。 现在要求你计算出卒从 AA 点能够到达 BB 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。 输入格式一行四个正整数，分别表示 BB 点坐标和马的坐标。 输出格式一个整数，表示所有的路径条数。 输入输出样例输入6 6 3 3 输出6 说明/提示对于 100 %100% 的数据，1 \le n, m \le 201≤n,m≤20，0 \le0≤ 马的坐标 \le 20≤20。 代码#include<bits/stdc++.h> using namespace std; long long a[25][25]; int mx[9]={0,1,1,-1,-1,2,2,-2,-2 ...

JavaAIO 基本介绍 JDK 7 引入了 Asynchronous I/O，即 AIO。在进行 I/O 编程中，常用到两种模式：Reactor 和 Proactor。Java 的NIO 就是 Reactor，当有事件触发时，服务器端得到通知，进行相应的处理 AIO 即 NIO2.0，叫做异步不阻塞的 IO。AIO 引入异步通道的概念，采用了 Proactor 模式，简化了程序编写，有效的请求才启动线程，它的特点是先由操作系统完成后才通知服务端程序启动线程去处理，一般适用于连接数较多且连接时间较长的应用 目前 AIO 还没有广泛应用，Netty 也是基于 NIO, 而不是 AIO， 就不详解 AIO 了，可以 参 考 <<**Java 新 一 代 网 络 编 程 模 型 AIO 原 理 及 Linux 系 统 AIO 介 绍** >>http://www.52im.net/thread-306-1-1.html 1.BIO、NIO、AIO 对比表

NIO与零拷贝1.零拷贝基本介绍 零拷贝是网络编程的关键，很多性能优化都离不开。 在 Java 程序中，常用的零拷贝有 mmap(内存映射) 和 sendFile。那么，他们在 OS 里，到底是怎么样的一个的设计？我们分析 mmap 和 sendFile 这两个零拷贝 2.传统 IO 数据读写Java 传统 IO 和 网络编程的一段代码 3.传统 IO 模型 DMA: direct memory access 直接内存拷贝(不使用 CPU) 4.mmap优化 mmap 通过内存映射，将 文件映射到内核缓冲区，同时， 用户空间可以共享内核空间的数据。这样，在进行网络传输时，就可以减少内核空间到用户空间的拷贝次数。如下图 mmap 示意图 5.sendFile 优化 Linux 2.1 版本 提供了 sendFile 函数，其基本原理如下：数据根本不经过用户态，直接从内核缓冲区进入到Socket Buffer，同时，由于和用户态完全无关，就减少了一次上下文切换 示意图和小结 提示：零拷贝从操作系统角度，是没有 cpu 拷贝 Linux 在 2.4 版本中，做了一些修改，避 ...

NIO 网络编程应用实例-群聊系统实例要求: 编写一个 NIO 群聊系统，实现服务器端和客户端之间的数据简单通讯（非阻塞） 实现多人群聊 服务器端：可以监测用户上线，离线，并实现消息转发功能 客户端：通过 channel 可以无阻塞发送消息给其它所有用户，同时可以接受其它用户发送的消息(有服务器转发得到) 目的：进一步理解 NIO 非阻塞网络编程机制 1.服务端import java.io.IOException; import java.net.InetSocketAddress; import java.nio.ByteBuffer; import java.nio.channels.*; import java.util.Iterator; public class GroupChatServer { //定义属性 private Selector selector; private ServerSocketChannel listenChannel; private static final int PORT = 6667; ...

SelectionKey与ServerSocketChannel的方法1. SelectionKey表示 Selector 和网络通道的注册关系, 共四种:int OP_ACCEPT：有新的网络连接可以 accept，值为 16int OP_CONNECT：代表连接已经建立，值为 8int OP_READ：代表读操作，值为 1int OP_WRITE：代表写操作，值为 4源码中：public static final int OP_READ = 1 << 0;public static final int OP_WRITE = 1 << 2;public static final int OP_CONNECT = 1 << 3;public static final int OP_ACCEPT = 1 << 4; 2. SelectionKey 相关方法 3. ServerSocketChannel ServerSocketChannel 在服务器端监听新的客户端 Socket 连接 相关方法如下 4.SocketChannel S ...

Selector选择器1.基本介绍 Java 的 NIO，用非阻塞的 IO 方式。可以用一个线程，处理多个的客户端连接，就会使用到 Selector(选择器) **Selector 能够检测多个注册的通道上是否有事件发生(注意:多个 Channel 以事件的方式可以注册到同一个Selector)**，如果有事件发生，便获取事件然后针对每个事件进行相应的处理。这样就可以只用一个单线程去管理多个通道，也就是管理多个连接和请求。 只有在 连接/通道 真正有读写事件发生时，才会进行读写，就大大地减少了系统开销，并且不必为每个连接都创建一个线程，不用去维护多个线程 避免了多线程之间的上下文切换导致的开销 Netty 的 IO 线程 NioEventLoop 聚合了 Selector(选择器，也叫多路复用器)，可以同时并发处理成百上千个客户端连接。 当线程从某客户端 Socket 通道进行读写数据时，若没有数据可用时，该线程可以进行其他任务。 线程通常将非阻塞 IO 的空闲时间用于在其他通道上执行 IO 操作，所以单独的线程可以管理多个输入和输出通道。 由于读写操作都是非阻塞的 ...

Nio实例与分析1.Java NIO 基本介绍 Java NIO 全称 java non-blocking IO，是指 JDK 提供的新 API。从 JDK1.4 开始，Java 提供了一系列改进的输入/输出的新特性，被统称为 NIO(即 New IO)，是同步非阻塞的 NIO 相关类都被放在 java.nio 包及子包下，并且对原 java.io 包中的很多类进行改写。【基本案例】 NIO 有三大核心部分：Channel( 通道) ，Buffer( 缓冲区), Selector( 选择器) NIO 是面向缓冲区 ，或者面向块 编程的。数据读取到一个它稍后处理的缓冲区，需要时可在缓冲区中前后移动，这就增加了处理过程中的灵活性，使用它可以提供非阻塞式的高伸缩性网络 Java NIO 的非阻塞模式，使一个线程从某通道发送请求或者读取数据，但是它仅能得到目前可用的数据，如果目前没有数据可用时，就什么都不会获取，而不是保持线程阻塞，所以直至数据变的可以读取之前，该线程可以继续做其他的事情。 非阻塞写也是如此，一个线程请求写入一些数据到某通道，但不需要等待它完全写入，这个线程同时可以去做 ...

Bio实例与分析1. Java BIO 基本介绍 Java BIO 就是传统的 java io 编程，其相关的类和接口在java.io BIO(blocking I/O) ： 同步阻塞，服务器实现模式为一个连接一个线程，即客户端有连接请求时服务器端就需要启动一个线程进行处理，如果这个连接不做任何事情会造成不必要的线开销，可以通过线程池机制改善(实现多个客户连接服务器)。 【后有应用实例】 BIO 方式适用于连接数目比较小且固定的架构，这种方式对服务器资源要求比较高，并发局限于应用中，JDK1.4以前的唯一选择，程序简单易理解 2. Java BIO 工作机制对 BIO 编程流程的梳理 服务器端启动一个 ServerSocket 客户端启动 Socket 对服务器进行通信，默认情况下服务器端需要对每个客户 建立一个线程与之通讯 客户端发出请求后, 先咨询服务器是否有线程响应，如果没有则会等待，或者被拒绝 如果有响应，客户端线程会等待请求结束后，在继续执行 3. Java BIO 应用实例实例说明： 使用 BIO 模型编写一个服务器端，监听 6666 端口，当有客户端连接时， ...