题目:http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1095 题意：这题要在一个无向正权图上找单源最短路，找到目标点后，还要求出到达这个点的最短路径的数量。有重边。 解法：dijkstra+DP。正权图找最短路首先想到dijkstra，然后考虑如何获得最短路数量和怎样处理重边。因为两点间只需一条最的路径就够了，因此记录图的时候可以考虑忽略其他权比较高的路径，只记录最短的那条。并且增加一个二元数组记录相邻点间的最短路径条数。此外有数组d记录起点到各点的最短距离，count记录到达这点的最短路径数。在dijkstra过程中，加入新节点后松弛没找到最短路的点的过程中，考虑如果松弛过程中d[i]==d[pos]+map[pos][i]，则count[i]+=count[pos]*p[pos][i]（此处之前错误写成了count[i]++，-_-!），如果d[i]>d[pos]+map[pos][i]，则count[i]=count[pos]*p[pos][i]。最后输出d[b],count[b]就行，注意各数组初始化，并且注意是两组输出之间有空行，最后一组输出后不用空行，仅换行，这里我也悲剧了一次。

昨天开始感冒，浑身无力，感觉不爽。今天写了两个，第一个是单调子序列，就不贴了。第二个是这个DP。题目:http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1094题目意思是求一个序列，这个序列满足三个一组，并且每组有一个属性m，这个m=min((a-b)^2+(b-c)^2+(a-c)^2)，其中a，b，c为序列中这组数的值。求得的序列是在N个元素的序列中的K组，使得这K组的m值和最小。解法：DP。考虑到如果abc顺序排列，则m只能取得(a-b)^2或(b-c)^2之一。类似01背包，将每个数当作每个物品，这个物品重量是1。因为决定一组数的m值尽取决于两个元素，因此第三个元素可以在没被选择的数里任意选择。状态转移：dp[i][j]=min(dp[i-2][j-1]+(a[i]+a[i-1])^2,dp[i-1][j-1])。这个状态转移的意思是，当考察了a中前i项并且最多组k队时的最小m值。这里实际上是在决定将a[i],a[i-1]加入组队，还是保持不变。因为这里每个人的重量为1，而最大容量相当于2*K因此，一定可以将背包装满。因此可以得到K组人。代码：点击下载

这个周末很颓废，几乎什么也没干。谴责一下自己。题目:http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1036这题就是要求一个稠密图上的最小生成树，并且求在这个生成树上的一个点，要求这个点到其余所有点的距离和最小。题目条件保证生成树唯一。解法：首先求最小生成树，用prim。每加入一个新的节点时，计算这个点到已经加入的所有点的距离。因为最小生成树中任意亮点的通路唯一，因此可以直接与prim中pre数组中的点到其余点做和求出。代码:依然点击这里下载

今天中午收到前天晚上在当当网定的书，当当的送书效率着实让我受惊若宠了一下。说来惭愧，三本书中两本是马上期中考试了的科目，因为觉着科目浮云，就连书都拖着到现在才买。当然，那本觊觎已久的APUE的到来还是让我兴奋了一下。今天早上自学完成OS之后还在愁上课没事干，下午这本圣经就突如其来的到手了。不过那700+页数的厚度还是很恐怖的。慢慢啃吧。啃完它再啃两本《UNIX网络编程》。言归正传，今天在逛M牛的博客的时候，发现了一个很好的算法题，正在感慨算法的精妙时，突然就在北邮的新oj发现了这么一道题，于是就做了。题目是说要求在内存1000K的条件下，完成记录一个10^6次方大小的数组的相同元素个数大于1%所有元素，并且按出现次数降序排列（出现次数相等则按元素从小到达排列）。这题的直观想法是，用一个数组记录每个值出现的次数，但题目中说每个数的范围是2*10^9，因此直接打消了我这个念头。1000K的内存甚至不足以记录所有10^6个数。因为这题明显改编自在M牛那看到的那道题，因此观察输入，将数组输入两遍，这就相当于我们只可以对原数组扫描两遍便得出结果。这里就要引出这个很牛逼的算法。第一遍扫描，我们用一张100大小的表记录某个元素的出现的次数，当这个表在扫描到某个元素时超过了100个记录时，则对表中的每个元素的出现次数减一，这样就能保证将表的元素数控制在100以下。当处理最后一个数时，无论是否超过100个元素，都将这个值添加到表中。这个第一遍找出的元素包含但不限于所有满足要求的结果。证明如下：反正，设总共有n个元素，且有一个x的出现次数p>=n/100。若x不在这个集合中，则必有在这个x之后又做了至少p次对所有出现次数减一的操作。因为每次操作减少100个元素，因此有减少了100p，而数组中总共有n个元素，且最后一个元素不会被去掉，因此100p<n，这与p>=n/100矛盾，得证。有了这样一个集合，我们就在第二遍输入的过程中简单记录在这个集合中的元素出现的次数，并且最后去掉所有不满足要求的元素（出现次数<1%，排序输出即可。因为这个表最大不超过100，因此是O(1)，因此不超过1000K的内存限制。code: #include<stdio.h>#include<stdlib.h>struct NODE{ int num,count; NODE *next;};int main(){ int n,in; int total,flag; int i,j,k; NODE *p,*q,*r; NODE head,ans; while(scanf(“%d”,&n)!=EOF) { head.next=NULL; ans.next=NULL; total=0; for(i=0;i<n;i++) { scanf(“%d”,&in); p=head.next; flag=0; while(p) { if(p->num==in) { p->count++; flag=1; break; } p=p->next; } if(!flag&&total<100) { p=new NODE; p->num=in; p->count=1; p->next=head.next; head.next=p; total++; } else if(!flag) { p=new NODE; p->num=in; p->count=1; […]

好久不写题了，写个试试。这个算Mathematica里吧，要不东西太少了。题目：http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1185大概是说，给你一个数组，求这个数组的逆序数。求逆序数的暴力方法：对于输入a[i]求a[1]…a[i-1]中大于于a[i]的数的个数,然后对所有这样的数求和。因而是o(n^2)。正常解法：首先想到排序，之后自然想到归并排序。考虑到归并排序中要对两个排列好的子串依次送入结果串，并且可以根据目前子串位置决定后面子串在前面子串的排名，因此可以得到逆序数。对于任意两个子串，后面子串中的数的位置不影响其对于前面子串的逆序数。而任意一个数的逆序数由在本子串的逆序数与对于前子串的逆序数的和。因此可以将两个子串排序，根据后面子串中数在前面子串中的插入位置决定其在前面子串的逆序数。对于本子串的逆序数由递归求得。代码：点击获取源文件

题目：http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1004 这题是说，给一个数列，问最少去掉多少个元素可以使这个数列成为前一半严格递增后一半严格递减的数列（前后两半共用中间最大的元素）。比如1,2,3,4,3,4，2,1，去掉第二个4之后得到1,2,3,4,3,2,1。 解法：最长单调子序列。 最长单调子序列求解用到DP，因为最长单调子序列具有最有子结构，例如考虑最优子序列l,如果l由l1、l2两个序列构成，则l1、l2都是原序列以l1最后一个元素为最后元素的序列的最长单调子序列。证明：如果l1或l2不是最优的，则找到最优的l3替换l1或l2，则新形成的序列比原l序列更长，因此l不是最优解，矛盾，因此l1、l2必须是最优解。根据这一性质，从前向后找最优子结构。dp(i)=max(dp(j)),j为0到i-1的，满足in(j)<in(i)的所有整数。 具体到这题首先正反两次求最长单调子结构，然后按照每一位找y=max(dp1(i)+dp2(i))则解为n-(y-1)。 代码: 点击这里下载