TCP回撤拥塞状态

2023-12-19 09:48
文章标签 tcp 状态 拥塞 回撤

本文主要是介绍TCP回撤拥塞状态，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

由于网络路径的变化或者延时的突然增加等，引发乱序并触发快速恢复或者RTO超时，TCP将进入TCP_CA_Recovery或者TCP_CA_Loss拥塞状态，如果随后检测到报文并没有丢失，TCP将撤销拥塞状态，恢复到之前的拥塞状态。

拥塞撤销初始化

其一，在进入快速恢复阶段时，不管是基于Reno或者SACK的快速恢复，还是RACK触发的快速恢复，都将使用函数tcp_enter_recovery进入TCP_CA_Recovery拥塞阶段。其中调用tcp_init_undo函数，初始化撤销操作，以便在检测到非必要进入恢复状态后（如乱序加重导致的误判、延时等），返回到原本的拥塞状态。

void tcp_enter_recovery(struct sock *sk, bool ece_ack)
{struct tcp_sock *tp = tcp_sk(sk);tp->prior_ssthresh = 0;tcp_init_undo(tp);...tcp_set_ca_state(sk, TCP_CA_Recovery);

其二，或者在RTO超时之后，满足以下任一条件：

  • 当前拥塞状态小于等于TCP_CA_Disorder，即还未进入恢复或者丢失拥塞状态；
  • 或者high_seq不在SND.UNA之后，即当前没有未完成的拥塞处理；
  • 或者当前拥塞状态已经为TCP_CA_Loss，但是还没有重传过报文；

调用tcp_init_undo函数初始化拥塞撤销操作，以便FRTO或者Eifel算法检测到为不必要的超时（RTO值过小）后，恢复之前的拥塞状态。注意，随后将high_seq设置为当前最大的发送序号SND.NXT，以示RTO超时恢复正在进行。

以上的三个判断条件，暗示了如果RTO发生在TCP_CA_Recovery拥塞状态，不初始化拥塞撤销操作，因为此时表明TCP_CA_Recovery状态的撤销未执行，发生的RTO超时，必定更加不能撤销。

void tcp_enter_loss(struct sock *sk)
{bool new_recovery = icsk->icsk_ca_state < TCP_CA_Recovery;tcp_timeout_mark_lost(sk);/* Reduce ssthresh if it has not yet been made inside this window. */if (icsk->icsk_ca_state <= TCP_CA_Disorder ||!after(tp->high_seq, tp->snd_una) ||(icsk->icsk_ca_state == TCP_CA_Loss && !icsk->icsk_retransmits)) {tp->prior_ssthresh = tcp_current_ssthresh(sk);tp->prior_cwnd = tp->snd_cwnd;tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk);tcp_ca_event(sk, CA_EVENT_LOSS);tcp_init_undo(tp);}tp->high_seq = tp->snd_nxt;

拥塞撤销初始化函数tcp_init_undo如下，记录进入TCP_CA_Recovery或者TCP_CA_Loss状态时的SND.UNA值到undo_marker变量中。变量undo_retrans记录可撤销的重传报文数量（非必要的重传数量）。

static inline void tcp_init_undo(struct tcp_sock *tp)
{tp->undo_marker = tp->snd_una;/* Retransmission still in flight may cause DSACKs later. */tp->undo_retrans = tp->retrans_out ? : -1;

进入TCP_CA_Recovery拥塞状态

如下tcp_fastretrans_alert函数所示，根据函数tcp_time_to_recover的返回结果判断何时进入TCP_CA_Recovery拥塞状态。

static void tcp_fastretrans_alert(struct sock *sk, const u32 prior_snd_una,int num_dupack, int *ack_flag, int *rexmit)
{switch (icsk->icsk_ca_state) {default:if (tcp_is_reno(tp)) {...tcp_add_reno_sack(sk, num_dupack);}tcp_identify_packet_loss(sk, ack_flag);if (!tcp_time_to_recover(sk, flag)) {tcp_try_to_open(sk, flag);return;}...tcp_enter_recovery(sk, (flag & FLAG_ECE));

函数tcp_time_to_recover依据丢包或者dupack/sack数量来判断是否进入快速恢复阶段。对于Reno算法，使用函数tcp_add_reno_sack增加dupacks数量；对于SACK算法使用tcp_sacktag_write_queue函数计算sack确认报文数量。以上调用的函数tcp_identify_packet_loss负责设置Reno和RACK算法的丢包数量。

如下判断，如果有丢包（lost_out），或者dupacks数量超出乱序级别，需要进入TCP_CA_Recovery状态。不同于基于dupack的算法，RACK基于时间判断丢包。

static bool tcp_time_to_recover(struct sock *sk, int flag)
{struct tcp_sock *tp = tcp_sk(sk);/* Trick#1: The loss is proven. */if (tp->lost_out)return true;/* Not-A-Trick#2 : Classic rule... */if (!tcp_is_rack(sk) && tcp_dupack_heuristics(tp) > tp->reordering)return true;return false;

对于RACK算法，在其超时处理函数中，如果tcp_rack_detect_loss检测到了丢包，网络中的报文数量（flightsize）必然发生了变化（原始报文或者重传报文丢失），套接口进入TCP_CA_Recovery状态。

void tcp_rack_reo_timeout(struct sock *sk)
{struct tcp_sock *tp = tcp_sk(sk);u32 timeout, prior_inflight;prior_inflight = tcp_packets_in_flight(tp);tcp_rack_detect_loss(sk, &timeout);if (prior_inflight != tcp_packets_in_flight(tp)) {if (inet_csk(sk)->icsk_ca_state != TCP_CA_Recovery) {tcp_enter_recovery(sk, false);

撤销TCP_CA_Recovery状态一（full）

如果在TCP_CA_Recovery拥塞状态接收到ACK报文，其ack_seq序号确认了high_seq之前的所有报文（SND.UNA >= high_seq），如上节所述，high_seq记录了进入拥塞时的最大发送序号SND.NXT，故表明对端接收到了SND.NXT之前的所有报文，未发生丢包，需要撤销拥塞状态，由函数tcp_try_undo_recovery实现。

static void tcp_fastretrans_alert(struct sock *sk, const u32 prior_snd_una,int num_dupack, int *ack_flag, int *rexmit)
{int fast_rexmit = 0, flag = *ack_flag;bool do_lost = num_dupack || ((flag & FLAG_DATA_SACKED) &&tcp_force_fast_retransmit(sk));...if (icsk->icsk_ca_state == TCP_CA_Open) {...} else if (!before(tp->snd_una, tp->high_seq)) {switch (icsk->icsk_ca_state) {...case TCP_CA_Recovery:if (tcp_is_reno(tp))tcp_reset_reno_sack(tp);if (tcp_try_undo_recovery(sk))return;tcp_end_cwnd_reduction(sk);break;}}

函数tcp_try_undo_recovery完成拥塞撤销，首先由tcp_may_undo进一步确认是否需要恢复拥塞窗口。undo_marker表明套接口进入了拥塞状态（TCP_CA_Recovery/TCP_CA_Loss），调整了拥塞窗口，否则没有必要进行恢复窗口操作。并且需要满足以下条件中的一个：

  1. undo_retrans等于0. 报文重传之后被D-SACK确认，表明这些重传为不必要的，原始报文未丢失。
  2. retrans_stamp等于0（重传报文时间戳retrans_stamp等于零）. 在进入拥塞状态后还没有进行过任何重传，或者重传报文都已送达。
  3. 接收到的ACK确认报文中的回复时间戳（rcv_tsecr）在重传报文的时间戳之前，表明是对于原始报文的确认，而不是对重传报文。
static inline bool tcp_may_undo(const struct tcp_sock *tp)
{return tp->undo_marker && (!tp->undo_retrans || tcp_packet_delayed(tp));
}
static inline bool tcp_packet_delayed(const struct tcp_sock *tp)
{return !tp->retrans_stamp || tcp_tsopt_ecr_before(tp, tp->retrans_stamp);
}
static bool tcp_tsopt_ecr_before(const struct tcp_sock *tp, u32 when)
{return tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr &&before(tp->rx_opt.rcv_tsecr, when);
}

以上条件确信网络并没有发生拥塞，恢复之前的拥塞窗口。函数tcp_try_undo_recovery执行拥塞窗口恢复（tcp_undo_cwnd_reduction）。

static bool tcp_try_undo_recovery(struct sock *sk)
{struct tcp_sock *tp = tcp_sk(sk);if (tcp_may_undo(tp)) { /* Happy end! We did not retransmit anything or our original transmission succeeded.*/DBGUNDO(sk, inet_csk(sk)->icsk_ca_state == TCP_CA_Loss ? "loss" : "retrans");tcp_undo_cwnd_reduction(sk, false);...} else if (tp->rack.reo_wnd_persist) {tp->rack.reo_wnd_persist--;}

另外，对于Reno算法，如果当前窗口中还有重传报文存在于网络中，保留retrans_stamp的值，避免这些重传报文触发dupack，再次引起错误的快速重传，此时需要保持拥塞状态不撤销，当再次接收到新的ACK报文（tcp_try_undo_recovery再次运行，但不会再执行以上的撤销拥塞窗口部分），确认SND.UNA大于high_seq后，进入TCP_CA_Open状态。

否则，如果SND.UNA大于high_seq，套接口直接恢复到TCP_CA_Open状态。

    if (tp->snd_una == tp->high_seq && tcp_is_reno(tp)) {/* Hold old state until something *above* high_seq* is ACKed. For Reno it is MUST to prevent false* fast retransmits (RFC2582). SACK TCP is safe. */if (!tcp_any_retrans_done(sk))tp->retrans_stamp = 0;return true;}tcp_set_ca_state(sk, TCP_CA_Open);tp->is_sack_reneg = 0;return false;

撤销TCP_CA_Recovery状态二（undo_partial）

对于TCP_CA_Recovery拥塞状态，如果ACK报文没有确认全部的进入拥塞时SND.NXT（high_seq）之前的数据，仅确认了一部分（FLAG_SND_UNA_ADVANCED），执行撤销函数tcp_try_undo_partial。

static void tcp_fastretrans_alert(struct sock *sk, const u32 prior_snd_una,int num_dupack, int *ack_flag, int *rexmit)
{/* E. Process state. */switch (icsk->icsk_ca_state) {case TCP_CA_Recovery:if (!(flag & FLAG_SND_UNA_ADVANCED)) {...} else {if (tcp_try_undo_partial(sk, prior_snd_una))return;/* Partial ACK arrived. Force fast retransmit. */do_lost = tcp_is_reno(tp) || tcp_force_fast_retransmit(sk);}if (tcp_try_undo_dsack(sk)) {tcp_try_keep_open(sk);return;}tcp_identify_packet_loss(sk, ack_flag);break;

如下函数tcp_try_undo_partial所示，与tcp_try_undo_recovery函数不同，这里没有使用tcp_may_undo进行撤销拥塞窗口的判断，而是使用了其中的一部分，即tcp_packet_delayed判断报文是否仅是被延迟了，忽略undo_retrans值的判断。其逻辑是在接收到部分确认ACK的情况下，只要tcp_packet_delayed成立，原始报文就没有丢失而是被延时了，就应检查当前的乱序级别设置是否需要更新（tcp_check_sack_reordering），防止快速重传被误触发。

另外，需要注意一点，在上一节函数tcp_try_undo_recovery的处理中，最终成功的进行了恢复，所以并不调整乱序级别。而这里的部分确认，则表明乱序级别低估了。

虽然不进行undo_retrans值的判断，但是，这里判断变量retrans_out（重传报文数量）是否有值，如果网络中还有发出的重传报文，不进行拥塞窗口的撤销操作，函数结束处理，等待重传报文被确认。

static bool tcp_try_undo_partial(struct sock *sk, u32 prior_snd_una)
{struct tcp_sock *tp = tcp_sk(sk);if (tp->undo_marker && tcp_packet_delayed(tp)) {/* Plain luck! Hole if filled with delayed* packet, rather than with a retransmit. Check reordering.*/tcp_check_sack_reordering(sk, prior_snd_una, 1);/* We are getting evidence that the reordering degree is higher* than we realized. If there are no retransmits out then we* can undo. Otherwise we clock out new packets but do not* mark more packets lost or retransmit more.*/if (tp->retrans_out) return true;

变量retrans_stamp记录了第一个重传报文的时间戳，如果已经没有了重传报文，清零此时间戳。函数tcp_try_keep_open尝试进入TCP_CA_Open状态，但是，如果套接口还有乱序报文或者丢失报文，将进入TCP_CA_Disorder拥塞状态。

        if (!tcp_any_retrans_done(sk))tp->retrans_stamp = 0;DBGUNDO(sk, "partial recovery");tcp_undo_cwnd_reduction(sk, true);NET_INC_STATS(sock_net(sk), LINUX_MIB_TCPPARTIALUNDO);tcp_try_keep_open(sk);return true;}return false;

撤销TCP_CA_Recovery状态三（dsack）

在函数tcp_fastretrans_alert中，对于处在TCP_CA_Recovery拥塞状态的套接口，ACK报文并没有推进SND.UNA序号，或者，在partial-undo未执行的情况下，尝试进行DSACK相关的撤销操作，由函数tcp_try_undo_dsack完成。

static void tcp_fastretrans_alert(struct sock *sk, const u32 prior_snd_una,int num_dupack, int *ack_flag, int *rexmit)
{switch (icsk->icsk_ca_state) {case TCP_CA_Recovery:...if (tcp_try_undo_dsack(sk)) {tcp_try_keep_open(sk);return;}tcp_identify_packet_loss(sk, ack_flag);break;case TCP_CA_Loss:...default:...if (icsk->icsk_ca_state <= TCP_CA_Disorder)tcp_try_undo_dsack(sk);

以下tcp_try_undo_dsack函数，如果undo_marker有值，并且undo_retrans为零，表明所有的重传报文都被D-SACK所确认，即重传是不必要的，执行拥塞窗口恢复操作。

/* Try to undo cwnd reduction, because D-SACKs acked all retransmitted data */
static bool tcp_try_undo_dsack(struct sock *sk)
{struct tcp_sock *tp = tcp_sk(sk);if (tp->undo_marker && !tp->undo_retrans) {tp->rack.reo_wnd_persist = min(TCP_RACK_RECOVERY_THRESH,tp->rack.reo_wnd_persist + 1);DBGUNDO(sk, "D-SACK");tcp_undo_cwnd_reduction(sk, false);NET_INC_STATS(sock_net(sk), LINUX_MIB_TCPDSACKUNDO);return true;}return false;

在DSACK判断函数tcp_check_dsack中，如果SACK序号块被认定为DSACK，并且undo_retrans大于零（进行过重传操作），并且，DSACK序号块的终止序号满足如下条件：

(prior_SND.UNA >= end_seq_0 > undo_marker)

表明对端接收到了原始报文和拥塞之后发送的重传报文，将undo_retrans递减一。

static bool tcp_check_dsack(struct sock *sk, const struct sk_buff *ack_skb,struct tcp_sack_block_wire *sp, int num_sacks, u32 prior_snd_una)
{   struct tcp_sock *tp = tcp_sk(sk);u32 start_seq_0 = get_unaligned_be32(&sp[0].start_seq);u32 end_seq_0 = get_unaligned_be32(&sp[0].end_seq);.../* D-SACK for already forgotten data... Do dumb counting. */if (dup_sack && tp->undo_marker && tp->undo_retrans > 0 &&!after(end_seq_0, prior_snd_una) &&after(end_seq_0, tp->undo_marker))tp->undo_retrans--;return dup_sack;

另外，在函数tcp_sacktag_one中，也进行如上的判断。

static u8 tcp_sacktag_one(struct sock *sk, struct tcp_sacktag_state *state, u8 sacked,u32 start_seq, u32 end_seq, int dup_sack, int pcount, u64 xmit_time)
{           struct tcp_sock *tp = tcp_sk(sk);/* Account D-SACK for retransmitted packet. */if (dup_sack && (sacked & TCPCB_RETRANS)) {if (tp->undo_marker && tp->undo_retrans > 0 &&after(end_seq, tp->undo_marker))tp->undo_retrans--;

进入TCP_CA_Loss状态

内核只有在报文的重传定时器到期时，在tcp_retransmit_timer函数中，进入TCP_CA_Loss拥塞状态。

void tcp_retransmit_timer(struct sock *sk)
{...tcp_enter_loss(sk);if (tcp_retransmit_skb(sk, tcp_rtx_queue_head(sk), 1) > 0) {

在函数tcp_enter_loss中，由tcp_init_undo初始化拥塞撤销操作。

void tcp_enter_loss(struct sock *sk)
{bool new_recovery = icsk->icsk_ca_state < TCP_CA_Recovery;tcp_timeout_mark_lost(sk);/* Reduce ssthresh if it has not yet been made inside this window. */if (icsk->icsk_ca_state <= TCP_CA_Disorder || !after(tp->high_seq, tp->snd_una) ||(icsk->icsk_ca_state == TCP_CA_Loss && !icsk->icsk_retransmits)) {tp->prior_ssthresh = tcp_current_ssthresh(sk);tp->prior_cwnd = tp->snd_cwnd;tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk);tcp_ca_event(sk, CA_EVENT_LOSS);tcp_init_undo(tp);}tp->high_seq = tp->snd_nxt;

撤销TCP_CA_Loss状态

对于处在TCP_CA_Loss状态的套接口，由函数tcp_process_loss进行处理，稍后介绍其中的拥塞撤销操作。

static void tcp_fastretrans_alert(struct sock *sk, const u32 prior_snd_una,int num_dupack, int *ack_flag, int *rexmit)
{case TCP_CA_Loss:tcp_process_loss(sk, flag, num_dupack, rexmit);tcp_identify_packet_loss(sk, ack_flag);if (!(icsk->icsk_ca_state == TCP_CA_Open ||(*ack_flag & FLAG_LOST_RETRANS)))return;/* Change state if cwnd is undone or retransmits are lost *//* fall through */

对于处在TCP_CA_Loss状态的套接口，如果ACK报文推进了SND.UNA序号，尝试进行TCP_CA_Loss状态撤销，由函数tcp_try_undo_loss完成。对于FRTO，如果S/ACK确认了并没有重传的报文（原始报文），同样尝试进入撤销流程，因为此ACK报文表明RTO值设置的不够长（并非拥塞导致报文丢失），过早进入了TCP_CA_Loss状态。

如果SND.UNA不在high_seq之前，表明恢复流程已经结束，进入TCP_CA_Loss状态时的发送报文（SND.NXT（high_seq））都已经被确认，执行tcp_try_undo_recovery。

static void tcp_process_loss(struct sock *sk, int flag, int num_dupack, int *rexmit)
{struct tcp_sock *tp = tcp_sk(sk);bool recovered = !before(tp->snd_una, tp->high_seq);if ((flag & FLAG_SND_UNA_ADVANCED) &&tcp_try_undo_loss(sk, false))return;if (tp->frto) { /* F-RTO RFC5682 sec 3.1 (sack enhanced version). *//* Step 3.b. A timeout is spurious if not all data are* lost, i.e., never-retransmitted data are (s)acked.*/if ((flag & FLAG_ORIG_SACK_ACKED) &&tcp_try_undo_loss(sk, true))return;...}if (recovered) {/* F-RTO RFC5682 sec 3.1 step 2.a and 1st part of step 3.a */tcp_try_undo_recovery(sk);return;

对于函数tcp_try_undo_loss，如果FRTO执行撤销操作，或者tcp_may_undo（参见以上介绍）检测到需要执行撤销，调用tcp_undo_cwnd_reduction函数恢复拥塞窗口。

/* Undo during loss recovery after partial ACK or using F-RTO. */
static bool tcp_try_undo_loss(struct sock *sk, bool frto_undo)
{struct tcp_sock *tp = tcp_sk(sk);if (frto_undo || tcp_may_undo(tp)) {tcp_undo_cwnd_reduction(sk, true);DBGUNDO(sk, "partial loss");NET_INC_STATS(sock_net(sk), LINUX_MIB_TCPLOSSUNDO);if (frto_undo) NET_INC_STATS(sock_net(sk), LINUX_MIB_TCPSPURIOUSRTOS);inet_csk(sk)->icsk_retransmits = 0;if (frto_undo || tcp_is_sack(tp)) {tcp_set_ca_state(sk, TCP_CA_Open);tp->is_sack_reneg = 0;}return true;}return false;

内核版本 5.0

这篇关于TCP回撤拥塞状态的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/511750。

相关文章

MySQL 中的服务器配置和状态详解(MySQL Server Configuration and Status)

MySQL 中的服务器配置和状态详解(MySQL Server Configuration and Status)

《MySQL中的服务器配置和状态详解(MySQLServerConfigurationandStatus)》MySQL服务器配置和状态设置包括服务器选项、系统变量和状态变量三个方面,可以通过... 目录mysql 之服务器配置和状态1 MySQL 架构和性能优化1.1 服务器配置和状态1.1.1 服务器选项
阅读更多...
linux进程D状态的解决思路分享

linux进程D状态的解决思路分享

《linux进程D状态的解决思路分享》在Linux系统中,进程在内核模式下等待I/O完成时会进入不间断睡眠状态（D状态）,这种状态下,进程无法通过普通方式被杀死,本文通过实验模拟了这种状态,并分析了如... 目录1. 问题描述2. 问题分析3. 实验模拟3.1 使用losetup创建一个卷作为pv的磁盘3.
阅读更多...
Java实现状态模式的示例代码

Java实现状态模式的示例代码

《Java实现状态模式的示例代码》状态模式是一种行为型设计模式,允许对象根据其内部状态改变行为,本文主要介绍了Java实现状态模式的示例代码,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来... 目录一、简介1、定义2、状态模式的结构二、Java实现案例1、电灯开关状态案例2、番茄工作法状态案例
阅读更多...
通过prometheus监控Tomcat运行状态的操作流程

通过prometheus监控Tomcat运行状态的操作流程

《通过prometheus监控Tomcat运行状态的操作流程》文章介绍了如何安装和配置Tomcat,并使用Prometheus和TomcatExporter来监控Tomcat的运行状态,文章详细讲解了... 目录Tomcat安装配置以及prometheus监控Tomcat一. 安装并配置tomcat1、安装
阅读更多...
Linux之进程状态&&进程优先级详解

Linux之进程状态&&进程优先级详解

《Linux之进程状态&&进程优先级详解》文章介绍了操作系统中进程的状态,包括运行状态、阻塞状态和挂起状态,并详细解释了Linux下进程的具体状态及其管理,此外,文章还讨论了进程的优先级、查看和修改进... 目录一、操作系统的进程状态1.1运行状态1.2阻塞状态1.3挂起二、linux下具体的状态三、进程的
阅读更多...
QT实现TCP客户端自动连接

QT实现TCP客户端自动连接

《QT实现TCP客户端自动连接》这篇文章主要为大家详细介绍了QT中一个TCP客户端自动连接的测试模型,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录版本 1:没有取消按钮 测试效果测试代码版本 2:有取消按钮测试效果测试代码版本 1:没有取消按钮 测试效果缺陷：无法手动停
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
hdu1565（状态压缩）

hdu1565（状态压缩）

本人第一道ac的状态压缩dp，这题的数据非常水，很容易过 题意：在n*n的矩阵中选数字使得不存在任意两个数字相邻，求最大值 解题思路： 一、因为在1<<20中有很多状态是无效的，所以第一步是选择有效状态，存到cnt[]数组中 二、dp[i][j]表示到第i行的状态cnt[j]所能得到的最大值，状态转移方程dp[i][j] = max(dp[i][j],dp[i-1][k]) ,其中k满足c
阅读更多...
状态dp总结

状态dp总结

zoj 3631  N 个数中选若干数和（只能选一次）<=M 的最大值 const int Max_N = 38 ;int a[1<<16] , b[1<<16] , x[Max_N] , e[Max_N] ;void GetNum(int g[] , int n , int s[] , int &m){ int i , j , t ;m = 0 ;for(i = 0 ;
阅读更多...
hdu3006状态dp

hdu3006状态dp

给你n个集合。集合中均为数字且数字的范围在[1,m]内。m<=14。现在问用这些集合能组成多少个集合自己本身也算。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.Inp
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2