p2p理财网站开发流程,新手怎么搭建网站,网站负责人拍照,制作网站源码【题目描述】 6046 数据包的调度机制 By OIer14wa随着 Internet的迅猛发展,多媒体技术和电子商务应用日益广泛,Internet上的服务质量(QoS,Qualityof Service)问题已越来越受到重视。网络中采用的数据包调度机制与网络的服务质量 QoS 有着密切的关系。研究表明传统的基于队列的调…【题目描述】 6046 数据包的调度机制 By OIer14wa随着 Internet的迅猛发展,多媒体技术和电子商务应用日益广泛,Internet上的服务质量(QoS,Qualityof Service)问题已越来越受到重视。网络中采用的数据包调度机制与网络的服务质量 QoS 有着密切的关系。研究表明传统的基于队列的调度机制已不能满足网络服务质量QoS 的需求。服务质量 QoS 取决于数据包的延迟。每一个数据包都有一个延迟惩罚值。由于数据包承载的数据不同,不同数据包的延迟惩罚值也可能不同。此外,数据包的延迟也和它的发送顺序有关。如果一个数据包被第K个发送,假设它的延迟惩罚值是D,则这个数据包的最终延迟是 (K - 1) * D。北京大学2012 级信息学院的同学在程序设计课堂上,设计了一种新的基于栈的数据包的调度算法。同学们通过栈的先进后出(Last in First out)的原理,改变数据包的发送顺序,以减小数据包的延迟总值。给定N 个等待调度的数据包,起始这N 个数据包排成一个队列等待发送。接着,这些数据包按序进栈,调度算法可以控制数据包的出栈顺序。因此通过栈,可以将后面的数据包先于前面的数据包发送出去。请你实现一个调度算法使N 个数据包的延迟总值最小。输入标准的输入包含若干组测试数据。输入第一行是整数T(1 T 1000)表明有T组测试数据。紧接着有T组连续的测试。每一组测试数据的第1行是 NN 100,表述数据包的个数。接着的 N 行,每一行是一个整数,第i 行表示数据包i的延迟惩罚值( 50 )。输出对于每组测试数据输出最小的延迟总值。样例输入1554322样例输出24一、题意分析枚举所有的可能性利用栈来控制数据包的发送顺序来得出最小的延迟惩罚值。二、算法说明枚举k是最后一个出栈根据栈这个数据结构的特点k如果是最后一个出栈k之前的一定在k之后的入栈前已经出栈了k之后的元素之后才入栈出栈。根据栈的这一特点我们可以把区间 [i--ij-1]枚举第k个元素最后出栈来划分区间划分为前后两个区间先是区间[i..k-1]然后是区间[k1..j]最后是k。三、数据结构四、算法分析f[i][j]表示的是区间[i--ij-1]j是延长的长度最小延迟值尝试把一个区间作为整体来看那么这个区间的最小惩罚值是f[i][k-i]a[k]*(len-1)f[k1][ilen-1-(k1)1](sum[ilen-1]-sum[k])*(k-i)但是我们可以看出len是表示ki--ilen-1枚举序列中的元素在当前序列中的位置而不是整个n长序列的位置那么*len-1会不会结果不对呢而且f[i][k-i]在整体的序列中也不定是第一个为什么不乘以他是第几个出发的呢我们来看后面这个(sum[ilen-1]-sum[k])*(k-i)sum是前缀和因为区间[k1][ilen-1-(k1)1]是当前区间f[i][j]的子区间而且他在这个区间中的是从第k-i个开始发数据包的所以要乘以k-i这就可以向大区间考虑了更新大区间的小区间表示的仅是他自身作为第一组的情况再加上(sum[ilen-1]-sum[k])*(k-i)就可以完整的表示出这个小区间在大区间中究竟是第几个位置了。五、代码与 调试 #includestdio.h#includestring.h#define INF 130#define N 111int a[N],f[N][N],n,t;int sum[N];void input(){ scanf(%d,n); for(int i1;in;i) { scanf(%d,a[i]); sum[i]sum[i-1]a[i]; }}int min(int a,int b){ if(ab) return(a); else return(b); } void DP(){ for(int len2;lenn;len) for(int i1;ilen-1n;i) { int tmpINF; for(int ki;kilen-1;k) { tmpmin(tmp,f[i][k-i]a[k]*(len-1)f[k1][ilen-1-(k1)1](sum[ilen-1]-sum[k])*(k-i)); } f[i][len]tmp; }}int main(){ scanf(%d,t); while(t--) { input(); DP(); printf(%dn,f[1][n]); } return 0;}
