描述
农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。 约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。 约翰的目标是合理安排每个fajo月包含的天数，使得开销最多的fajo月的开销尽可能少。
输入
第一行包含两个整数N,M，用单个空格隔开。 接下来N行，每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。
输出
一个整数，即最大月度开销的最小值。
输入样例 1
7 5
100
400
300
100
500
101
400

输出样例 1
500

代码：
#include<cstdio>
#include<algorithm> 
using namespace std;
int a[100001],n,m;
bool pd(int x)
{
	int i,sum=0,tot=1;
	for(i=1;i<=n;i++)
	  if(sum+a[i]>x)//如果总的开销大于x，则tot++，说明已经是下一个月 
	  {
	  	sum=a[i];
	  	tot++;
	  }
	  else
	    sum+=a[i];
	return tot<=m;//如果tot小于m，说明有的月还可以拆分 
}
int main()
{
	int mid,i,ans,j,l=0,r=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		l=max(l,a[i]);//开销最小不会小于每天的最大开销 
		r+=a[i];//开销最大不会大于每天开销的和 
	}
	while(l<=r)//二分每个月最大开销 
	{
		mid=(l+r)>>1;
		if(pd(mid))//判断是否可行 
		{
			ans=mid;
			r=mid-1;
		}
		else
		  l=mid+1;
	}
	printf("%d",ans);
	return 0;
}

MPI 通讯开销测算
一个简单的pingpong程序测试mpi消息通讯的开销
随着科技的进步，集群单节点计算能力的提高，似乎通讯开销成了并行计算中dominant，再提高计算能力对于并行的增益似乎效果不明显，限制性能的瓶颈从处理器计算能力上转移到通讯开销上。显然，此时设法降低MPI消息通讯带来的时间消耗，成为了当务之急。
因此，写了一个极其简单的pingpong并行程序来测试消息通讯带来的开销。
基本思想
所谓的pingpong，顾名思义就是找一个数据包不断地在两个节点之间丢来丢去，想打乒乓球一样。

我们在程序中定义两重循环，外重循环定义数据量大小，从1kb到100m，涨幅为100kb，内层循环对于每一固定大小的数据跑100个来回，最后取平均值，作为这个大小的数据的传输时间。最后，以数据量大小为横轴，时间为纵轴，plot一下。
准备工作
我们连接了机房的两台电脑，作为实验环境。主要设置了SSH免密登录和NFS共享目录。

一个简单的代码如下：
/**
 * pingpong程序，用于测试点点传送的速度
 */
//32位系统中，一个int占4B(sizeof(int))，1KB=250int，1M=250000int
//1M=1000kb，100M = 10e5kb
//使用N表示数据量大小为 N kb
//程序运行时，首先要把目录下的data.txt删除
#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#include <string.h>

//#define N 4 //外层循环数据量大小改变，使用动态数组来实现
#define m 100 //定义pingpong的回合
#define debugflag 0

int main (int argc, char *argv[]) {


	int myrank,i,nprocs;
	double pingpongSize,aver_tcost,total_t,Ts[m];
	double st, et, time_cost;
	double N, Num_int;
	int *pingpong;
	char file_name[10];

	MPI_Init(&argc, &argv);//初始化MPI环境
	MPI_Comm_size(MPI_COMM_WORLD, &nprocs);//获取总进程数
	MPI_Comm_rank (MPI_COMM_WORLD, &myrank);//获取本地进程编号
	MPI_Status status;

	//int opposite_rank;  opposite_rank = (myrank == 0) ? (1) : (0);
	FILE *fp;
	sprintf(file_name,"data_from_rank%d.txt",myrank);
	fp=fopen(file_name,"w+");


//	for(N=1; N<=1e4; N=N+1e3) {
	for(N=1e-3; N<=1e5; N=N*2){
		total_t = 0.0;
		pingpong = (int*)malloc( N*1000);//开辟 N kb的内存
		Num_int = ( N*1000)/sizeof(MPI_INT);
		if(!pingpong) {
			printf("创建pingpong失败！\n");
			exit(1);
		}
	//	int pingpong[N] = {0};//随便赋值
	
		for(i=0;i<Num_int;i++)
		{
			pingpong[i] = 999;//赋值，并非必要
	//		printf("%d,%d",i,pingpong[i]);
		}
	
	//	pingpong[0] = 999;
		if(myrank==0)
		{
			printf("开始 %lfkb/1e5kb 数据传送……\n",N);
		}
		
		for(i=0; i<m; i++) {
			MPI_Barrier(MPI_COMM_WORLD);//同时开始计时
			st = MPI_Wtime();
			if(myrank==0) {
				MPI_Send (pingpong, Num_int, MPI_INT, 1, i, MPI_COMM_WORLD);
#if debugflag	
				printf("第%d回合:%d发送数据完成……\n",i+1,myrank);
#endif
			}
			if(myrank==1) {
				MPI_Recv (pingpong, Num_int, MPI_INT, 0, i, MPI_COMM_WORLD, &status);
				MPI_Send (pingpong, Num_int, MPI_INT, 0, i, MPI_COMM_WORLD);
#if debugflag				
				printf("第%d回合:%d接收和发送数据完成……\n",i+1,myrank);
#endif				
			}

			if(myrank==0) {
				MPI_Recv (pingpong, Num_int, MPI_INT, 1, i, MPI_COMM_WORLD, &status);
#if debugflag				
				printf("第%d回合:%d接收数据完成……\n",i+1,myrank);
				printf("第%d回合succeed! The time of cost is %lf\n\n",i+1,time_cost);
	//			printf("一个int占用:%ld B",sizeof(myrank));
#endif	
			}
			MPI_Barrier(MPI_COMM_WORLD);//保证进程1计算的时间也准确
			et = MPI_Wtime();
			time_cost = et-st;
			
			total_t = total_t+time_cost;
			Ts[i] = time_cost;

		}
		aver_tcost = total_t/m;
		
		
		pingpongSize = N/1e3;//单位换算成M
	//	printf("%lf个int的数据量大小为%lf M!\n",N,pingpongSize);

		fprintf(fp,"%lf,%lf\n",pingpongSize,aver_tcost);
		
		free(pingpong);
		
		if(myrank == 0){
			printf("%lfM 数据包发送接收回合完成……\n",pingpongSize);
			printf("%lfkb 的数据量的传送时间平均时间为: %lf \n\n",N,aver_tcost);
			
		}
		
		
	}
	fclose(fp);

	MPI_Finalize ();//结束MPI环境
	return 0;
}


实验和结果
将实验结果，画一下图，如下：

从结果上可以看到，整体上看，通讯开销随着数据量大小呈现一个的关系，我们可以很容易地用线性函数去做线性fit，得到了T = 0.01711X+0.0004188这个这样一个关系，可靠程度：误差平方和为4.79e-6，均方根误差为0.0003263，确定系数约为1，说明这个拟合是很可靠的。

分析一波这个拟合结果，我们大概能知道每增加100m的数据，大概需要增加1.7s。所以，100M的数据，跑一百个回合，大概需要三分钟。
并行计算通讯启动时间测算
简述
我们知道，并行计算的消息传递不可能一上来就开始传数据，它是有一个启动时间的，就像游泳前的热身。那么这个启动时间是多少呢？又该怎么测算呢？

依然是pingpong的例子，只不过为了看出1kb之前的这个微小的数据变化段通讯时间情况，我修改了程序中数据量大小增加的情况，前面以double的形式从1B增加到1KB，往后，以5M为间隔，逐渐将数据量增加到100M。
数值实验
分别测定了双节点，和单节点的情况，结果如下。
双节点
首先使用两台节点跑了这个程序。

为了看到初始的那一小段的情况，我们将绘制的plot图（近似线性）在开始断不断地放到，最后发现，通讯时间在1kb左右的地方开始激增。


从图上，我们可以看出，最开始的一段有一个抖动，这是意外。为了更好地体现这种通讯时间前面一小段几乎水平不变，后面呈线性增长的这种“拐角”情况，我们不妨来画一下双log图来呈现。为什么用双log图呢？很容易想到，如果趋势是线性的，那么双log后，展现出来还是线性的，如果是常数关系，那么双log后还是常数关系。log函数能使数据在展现上变得更加均匀，避免了“头重尾轻，细节模糊”的情况。双log函数，能够将细节的地方的展现和刻画出来，结果如下。



可以看得出来，开始一段时间的通讯时间几乎没有改变，通讯启动时间大概为0.000165s，即0.165毫秒。
单节点
对于单节点，不涉及两台机器的通讯，我们重复了上面的测算过程，结果如下：


上面直接plot的图之后再方法局部的图，发现有一个比较反常的点，估计是跑程序的时候，受到了别的因素的干扰。如果去掉这个离群点来考虑，它也是有这样一种“前平后翘”的“对勾”走势。我们再来看看双log图。

双log图使数据呈现得更加“集中”，也使得原来离群得厉害的点变得那么不靠谱。从这里，因为开始时相对比较平坦（排除其他因素影响的情况下），我们假设开始那一段没有增长，姑且就可以把开始那段的值作为程序的启动开销。这里，可以看到，单击上，并行程序运行时，启动的开销大概为2e-6s，即0.002ms，基本上是两台机子通讯启动的百分之一。

由那些不正常抖动的情况来看，并行对于资源的要求还是很敏感的，比如说当你在跑程序时，有其他资源抢占了资源，就容易造成通讯开销的增加。

一、根路径开销和本地路径开销

本地路径开销 也就是端口开销，和端口速率有关，越快越低。

交换机的每个端口都有一个端口开销（Port Cost） 参数， 此参数表示该端口在STP中的开销值。 默认情况下端口的开销和端口的带宽有关，带宽越高，开销越小。从一个非根桥到达根桥的路径可能有多条，每一条路径都有一个总的开销值，此开销值是该路径上所有接收BPDU端口的端口开销总和（即BPDU的入方向端口），称为路径开销。非根桥通过对比多条路径的路径开销，选出到达根桥的最短路径，这条最短路径的路径开销被称为RPC（Root Path Cost， 根路径开销），并生成无环树状网络。 根桥的根路径开销是0。
即累计根路径开销最小的端口就是根端口。端口收到一个 BPDU 报文后，抽取该 BPDU 报文中累计根路径开销字段的值，加上该端口本身的路径开
销即为累计根路径开销。
从非根桥到根桥的路径可能有很多条，从该端口(包括该端口)到根桥的路径上所有出端口的端口开销总和就是根路径开销

如上图:s2中eth0/0/1端口的根路径开销就是20+18=38,eth0/0/2端口的根路径开销就是39.所以0/0/1是根端口。

原文地址 http://www.daileinote.com/computer/math/0f

最小开销路径(Min Cost Path)(MCP)，给出一个开销矩阵cost，求得从cost[x][y] 到 cost[i][j] 的最小开销。比如下图



从 (0,0) 到 (2,2) 的最小开销为 8 (1 + 2 + 2 + 3)



想要到达 (m, n)，必须经过 (m-1, n-1)，(m-1, n)，(m, n-1) 其中一个， 所以 minCost(m, n) = min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n]

下面是没有解决重叠子问题的例子

#include <stdio.h>
#include <string.h>
#define dl_max(x,y) ((x) > (y) ? (x) : (y))
#define MAX_COST 1024   // 这里定义一个上限
int dl_min(int x, int y, int z) { if (x < y) return x < z ? x : z; else return y < z ? y : z;}
int min_cost(int cost[3][3], int m, int n)
{
    if (m < 0 || n < 0)
        return MAX_COST;

    if (m == 0 && n == 0)
        return cost[m][n];

    return cost[m][n] + dl_min(min_cost(cost, m-1,n), min_cost(cost, m,n-1), min_cost(cost, m-1,n-1));
}

int main()
{
    int cost[3][3] = {
        {1, 2, 3},
        {4, 8, 2},
        {1, 5, 3}
    };

    printf("min cost: %d\n", min_cost(cost, 2, 2));
}

                                    mC(2, 2)
                          /            |           \
                         /             |            \             
                 mC(1, 1)           mC(1, 2)             mC(2, 1)
              /     |     \       /     |     \           /     |     \ 
             /      |      \     /      |      \         /      |       \
       mC(0,0) mC(0,1) mC(1,0) mC(0,1) mC(0,2) mC(1,1) mC(1,0) mC(1,1) mC(2,0)

上面有很多重复计算的问题，跟其他动态规划问题一样，这里满足 最优子结构 和 重叠子问题，可以构建 arr[][]解决

#include <stdio.h>
#include <string.h>
int dl_min(int x, int y, int z) { if (x < y) return x < z ? x : z; else return y < z ? y : z;}
int min_cost(int cost[3][3], int m, int n)
{
    int     i,j,sum[3][3];

    sum[0][0] = cost[0][0];

    //计算第一列
    for (i = 1; i <= m; i++)
        sum[i][0] = sum[i-1][0] + cost[i][0];
    
    //计算第一行
    for (i = 1; i <=n; i++)
        sum[0][i] = sum[0][i-1] + cost[0][i];

    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            sum[i][j] = cost[i][j] + dl_min(sum[i-1][j], sum[i][j-1], sum[i-1][j-1]);
        }
    }

    return sum[m][n];
}

int main()
{
    int cost[3][3] = {
        {1, 2, 3},
        {4, 8, 2},
        {1, 5, 3}
    };
    printf("min cost: %d\n", min_cost(cost, 2, 2));
}

时间复杂度为 O(mn)

原文地址 http://www.daileinote.com/computer/math/0f​​​​​​​